Link: Indian Computing Olympiad Archives 2009
The problem description is as such:
"You are given a square grid of positive and negative numbers. You have to start at the top left corner of the grid and find a path to the bottom-right corner. In each step, you are only allowed to move one position to the right or one position down. As a special bonus, you are allowed at most one move that can be either to the left or up. Note that you are allowed to visit a position more than once as a result of this special move.
Your aim is to find such a path that has the maximum weight, where the weight of a path is the sum of all the numbers visited along the path."
Sample Input:
4
12 -16 10 -12
-16 13 -14 7
7 -4 16 -15
-7 16 -9 8
Sample Output:
32
This is what I have thought of till yet.
The first approach is the more obvious brute force search, probably recursive. But the running time would be exponential so no point in considering.
Besides this, I thought of using Dynamic Programming to create a 2D array (lets call it dp) in which each element would store the best weight up till that position in the grid. However, this would not directly provide where to use the one additional special move provided. I thought of maybe reconstructing the path using the best weight till dp[n][n]. In the example given, the best path would be 20 -> [12,-16,13,-4,16,-9,8]. Now we can find the two elements which have the greatest sum, in this case 16 and -4 and 16 give 12. So if in this path we had moved left at 16 and gone to -4, then back to 16, the total would be 32 which is our answer. However this algorithm may not always work.
If there is a path [10,-2,-1,4,1] with total weight 12, and another with [10,0,-2,2,1] total weight 11, then the algorithm would use the first path and give an output of 12+8 = 20. However, using the second path the total weight would have been 21.
So now after spending an hour on this I have no idea what the solution could be. Any hints please?
Thanks!
P.S: Keshav, this was the ZCO paper you gave in 2008 right? Were you able to solve it back then? :P