I was hoping to ask for a bit of advice on a USACO question. It is the Number Triangles problem in section 1.4. The problem statement can be found here
My initial idea is that it cannot be avoided that this tree-like structure must be traversed in all possible ways, they've listed (downwards left diagonal or downwards right diagonal).
In the example input they give in the problem statement, with 5 rows, it can be worked through that there are 16 possible traversals of the tree. In an example of 4 rows, there are 8 possible ways, ..., and in an example with 1 row there is one possible way. So there are 2^(r-1) possible traversals that need to be checked for maximum sum.
I believe this can be solved if I can find out a way to represent static trees in an array data structure, where I will traverse each possibility given the constraints they've laid out.
That's all fine and dandy, and I think is realistic to do but the problem statement is in the last section of chapter 1, called Introduction to Binary Numbers. Because of this, I cannot for the life of me think of if this is the way the authors intended me to go about solving the problem or if there is an approach I am completely blind to. If I were to solve the problem using the approach mentioned above, I could use binary representations for each node but I see no particular reason to do so when the same could be done with decimal representations. Here is my thought process on paper to show I have put some time into the problem.
If you have any input you could share, I would be most grateful. Also, I've only been working on this problem today. I almost feel like I am cheating by asking you for hints. When you are solving problems, how much time do you generally give yourself to think alone before reaching out for help. Am I doing the right thing?
Thank you for reading.
Suppose that you are in the top and you want to compute the optimal way to get to the bottom. You have 2 options you either move down and to the left, or down and to the right. At least one of these options will lead you to construct an optimal solution. Now suppose that in a sort of magical way you were told what option is optimal ( down and then to the right for example ), if you somehow knew how to reach to the bottom from that point in an optimal way, you would have solved your problem, the answer would be val[ 1, 1 ] + optimal_path( 2, 2 ). Observe that the options you have at each step are only 2 and that the original problem can be easily analysed to smaller instances of the same problem ( going from ( 1, 1 ) to the bottom is pretty similar to going from ( 2, 2 ) to the bottom ).
( This problem is a classic dynamic programming, so you should be a bit familiar with the technique, if you don't know dynamic programming you can read the topcoder tutorial which i think is very helpful )
Thank you for the reply. :D
The thing that troubles me is that this problem was given in a section titled "Introduction to Binary Numbers", at the end of chapter 1. The section on Dynamic Programming is not until the end or middle of chapter 2.
Is there an approach to this problem appropriate for the context of the section -- one that deals with binary numbers?
Well i solved that problem with dynamic programming, but it can be solved by producing binary numbers in a O( 2^n ) fashion. As we said you have 2 options at each point let 0 indicate going down-right and 1 down-left. Your path will be n — 1 steps long, so you 'll make n — 1 decisions, if you concatenate all the decisions for each path you 'll get a binary number, so by producing all the binary numbers up to 2^ n — 1, you have all the series of decisions possible and it takes just O( n ) time to check each one of them and find the optimal solution. That's possibly why this problem was put in that section, but if you want a better solution, then you 'll have to go with dp :)