Definitely MAGIC

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:

OK, straight forward, the question doesn’t ask us to maximize Harry’s path value. We must make sure he is alive! (😛). The question is to assign minimum amount of strength at the beginning of the grid so that Harry can choose a path and collect the Sorcerer’s stone (while being alive, this seems redundant). The regular DP — maximizing the path value doesn’t work. Here’s an example, suppose the grid is

 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;
    }
}