Problem: http://www.spoj.com/problems/AMR11A/

This problem really got me thinking, at first glance problem seems pretty do-able, but after two wrong submissions, I realized, my dynamic programming (DP) state is completely wrong! Finally when I solved it, it made my day.

If you haven’t tried, do so. You’ll have fun.

Solution:

 0   -1
-2 0

So Harry starts with 1/0 strength (hypothetical), then either path he takes, his strength decreases (<=0) and he dies. So we must assign him a minimum strength of 2.

The DP state is surprisingly simple, suppose we are at the cell (r-1,c-1) and we want to go to (r,c). For Harry to be alive, it is sufficient for him to end up at (r,c) with resultant strength ‘1’. So we choose the path that maximizes Harry’s strength (alternately if negative values, we choose the one which decreases his strength least).

Suppose that the cell values are in `s[1…..r][1….c]`

Initialization — last row:

for(int i = c - 1; i > 0; –i) {
s[r][i] = s[r][i+1] — s[r][i];
if(s[r][i]0; –i) {
s[i][c] = s[i+1][c] — s[i][c];
if(s[i][c]<1) {
s[i][c] = 1;
}
}
}

for other rows and columns:

for(int i = r - 1; i > 0; –i) {
for(int j = c - 1; j > 0; –j) {

if(s[i + 1][j] > s[i][j + 1])
s[i][j] = s[i][j + 1] — s[i][j];
else
s[i][j] = s[i + 1][j] — s[i][j];
if(s[i][j] < 1)
s[i][j] = 1;
}
}

Artificial Intelligence Researcher | Developer

Artificial Intelligence Researcher | Developer