I can try to explain my solution.

Move is define as moving to a neighbouring cell with adjacent border. Now, let's state a couple of facts (I believe they are easily believable/provable):

• The amount of moves in which a cell disappears is equal to the minimal distance to the non-existent cell on the grid. Let's call this a value of the cell.
• Any cell has larger or equal value than the cell above it.
• From any cell one can obtain the shortest path to non-existent cell by moving only horizontally over some distance and then moving only vertically.

Due to these facts, we can now deduce that we are only interested in calculating values of the bottom row and picking maximum of it. For every cell in the bottom row, we are only interested in minimum of all paths described above. As such, for a cell (i, 1):

value(i, 1) = max(h[i], max(1 + h[i-1], 2 + h[i-2], ..., i-1 + h[1], i), max(1 + h[i+1], 2 + h[i+2], ..., (N-i) + h[N], (N-i+1))

First term is O(1) for a cell, while second and third can be precomputed in advance from left and right sides by noting that for neighbouring cell in the direction of increasing amount of terms, all previously existent terms are increased by one and we just add a single new one.

In brief: Use prefix and postfix summs

Ok, I think I got it.

worst stores t[j]-j in the worst case from left to right. So, if t[i]-i is greater than worst, we simply assign res[i] = t[j]-j+i , else res[i] = t[i] .This way, we can ensure that the lowest value is assigned that falls on left of t[i] . (j<=i)

This works because, if t[j]+i-j > t[j+1]+i-j-1 then t[j] >= t[j+1], which is true in this case.

Phew! Such twisted logic. I'm respecting people who solved such problems even more now :)

edit: Another way(and much more intuitive and understandable) is: we are trying to find min ( t[i-j] + j ), for each j, for a fixed i. This minimum value is res[i].

Let p=i-j. So, j=i-p Now, the statement becomes min(t[p]-p) + i for each p, for a fixed i .