Money Prize Ii

[A.J]

did anyone solve December 2003 problem no 3?
i have an inefficient method that recurses all possible paths for the first couple then dp's it for the seond couple.

[McKenzie]

Money Prize is a textbook DP problem. Wikipedia has a good Dynamic Programming article. Poke around with it for a bit then come back to the problem. If you are still stuck I can drop a few bread crumbs.

[A.J]

I can easily finish Money Prize, but i am talking about Money Prize II.
It is harder since it not only requires dp, but also a recursive function to recurse every first path(if i am not mistaken)
I am pretty sure there is a method to do this that might be WAY over my head, but I am trying to find this method.

[zylum]

Recursion might be fast enough depending on how you do it.. If you use diagonals it probably will be too slow. Either way this problem was most likely designed to be solved using dp. Look here in the advanced section. It describes how to solve a similar (slightly more difficult) problem with dp.

hope that helps

[McKenzie]

Oops, sorry about that, the "Ii" threw me off.

Straight recursion gives you about 4^10 recursive calls for the 10x10 grid or about 1000000 calls. I'm sure there are ways to prune this, but as it stands, that's no good. Consider though that the couples will always be on the same diagonal at any number of steps. At each diagonal the couples can only be in two of the squares this gives you 10^2 + 9^2 +... or 385 unique states. I can clarify more but I don't want to rob you of the fun of breaking the rest.

[A.J]

SO you are saying that after any N moves, the couple will always be on the same diagonal?
Hmmmmmmm............... I'll try seeing how that helps me

[zylum]

For the 10x10 case, each couple will have to move 18 steps to reach the other corner.. Most of the time they have 2 directions to move, either up or right.. So that's about 4^18 possible routes.. You may notice that if the couples paths intersect, you can eliminate that path as explained in the article i linked to above. This will cut the search space considerably but im still not sure recursion will work here.. This is definitely a problem for dp imo..

[McKenzie]

Ya, I realized that my math was a bit off, but it's not quite 4^18 either, because at the edges they only have one choice, but it's big and bad though (my 385 should be 670 or 335 too.)

Why the diagonals matter: One of the key elements of DP is to see the problem in terms of stages. In a 10x10 grid there are 19 diagonals, and thus 19 stages, and it is enough to look one stage back to make calculations. I would store the maximum values for each possible state something like:

code:

Diagonal #    Male Pos    Female Pos   Total 0                   0               0                 ? 1                   0               0                 ? 1                   0               1                 ? 1                   1               1                 ? 2                   0               0                 ? 2                   0               1                 ? 2                   0               2                 ? 2                   1               1                 ? 2                   1               2                 ? 2                   2               2                 ? ...

Where I see the position as 0 is top left of the diagonal.

The problem with most DP is that it is really hard to see the stages. If you know how to do the straight recursion then simply add memoization to your solution and it will run very very fast.