Of these problems, 18 is fairly trivial. With enough work, you could even solve it with a piece of paper and pencil. 67 is orders of magnitude more diffucult. There are 299 differet possible paths from bottom to top, and to test every one would take more computing power than that in the world and more time than that in the universe. I finally realized that the way to solve it is to cache every value as it's calculated.
Start on the second to bottom row, and for each of the 99 columns, find the maximum path to the bottom, which is trivial because there is only two paths for each column. Save these values. Now when you move to the third bottom row, all of the maximum paths beyond the second bottom row are already calculated. Again it's trivial because each number only has two paths to the precomputed values you already have. This allows the solution to be solved well under the maximum minute.
My solution for both of these problems use the same code, just recompile it, defining TRISIZE as the number of rows in the triangle.
cc -DTRISIZE=10 018.c
./a.out << 018.input
cc -DTRISIZE=100 018.c
./a.out << 067.input
018.c
018.input
067.input
Return to list of solutions
Comments (0)
You don't have permission to comment on this page.