ACM ICPC Amritapuri Regionals 2011 A

I am trying to solve this problem :

Here is a link to my solution

I am first using the usual dp method of finding best path through a 2D matrix and then moving back on the path t0 find the lowest energy point on my selected path.

I am getting Wrong answer

Your approach is not wrong, but you are missing one point. You have fixed S[0][0] to 1. Suppose your solution gives Y as an answer. Then, my argument is that, there may exist a different value X as a starting value, where 1 < X < Y, and least value in the path is greater than 0.
The solution is to perform a binary search over possible value of S[0][0] and see if we can get to (R-1,C-1) without reaching zero value.
Here is the link to modified solution . It gets AC on ICPC Live Archive, but TLE on SPOJ.

Homework for you: What if you started from S[R-1][C-1] and went back to S[0][0]? The optimum result will be obtained, when Harry manages to get at S[R-1][C-1] with value 1 (fix S[R-1][C-1] to 1). So, if you implemented a DP in backward fashion, value at (0,0) will be your answer. Here, you don’t have to perform binary search. So, it won’t get TLE on SPOJ. Guaranteed.

1 Like