adityagamer's blog

By adityagamer, history, 20 months ago, In English

Source: Interview

There is grid 'a' of size n*m. There is a guy on cell (1,1) and he wants to reach (n,m). He can move either down or right. Initially, he has health H. If he gets on cell (i,j), then a[i][j] is added to his health. If his health becomes less than or equal to 0, he dies.

Find the minimum value of H so that he can reach the cell (n,m).

I told her binary search but she asked to remove log factor.

How to solve this?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think you could use dp, where dp[i][j] contains cost of reaching (i, j) using optimal path. By cost I mean minimum value of dp on the path to (i, j). I believe that if at the end dp[n][m]<0, H is equal to -dp[n][m], if dp[n][m]=0, H=1, else H=0. I'm not sure it's 100% correct but I think general idea might be helpful.

»
20 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Define $$$D[i][j]$$$ as the minimum health required to start with to travel from $$$(i, j)$$$ to $$$(n, m)$$$.

Then, $$$D[i][j] = max(0, min(D[i + 1][j], D[i][j + 1]) - A[i][j])$$$.