Programming again

The problem is given here.

Def 1: A zig-zag path is a path starting from $(i,j)$ which moves according to the following rule $(i,j)\rightarrow ((i+1)\mod 2, j)\rightarrow ((i+1)\mod 2, j+1)$. This rule may be repeated as many times as we like.

Claim: Suppose we are at $(1,j)$ after making two consecutive right moves. Then we are forced to move $(1,j+1)\rightarrow ... \rightarrow (1,m)\rightarrow (2,m)\rightarrow ... \rightarrow (2,j-1)$. Call such a path a forced path.

Then the path that we must take will firstly consist of a zig-zag path starting from $(1,1)$ (possibly of length $0$) followed by a forced path (possibly of length $0$). 

Suppose for any cell $(i,j)$ we have pre-computed the time needed to complete the forced path in $f[i,j]$, and the time needed to zig-zag to this cell $z[i,j]$ from $(1,1)$. We define $t[i,j]$ to be the minimum time needed to visit each cell exactly once given that we have zig-zaged to $(i,j)$. Then

$$t[i,j]=z[i,j]+\min(t[(i+1) \mod 2, j+1], f[i,j+1])$$

The problem now reduces to computing $z[i,j]$ and $f[i,j]$ efficiently, i.e. in $O(m)$. The problem of computing $z[i,j]$ can be done in $O(m)$ by directly simulating the unique zig-zag path.

We now focus on the only remaining task of computing $f[i,j]$, i.e. the time to complete the forced path starting at $(i,j)$. This is where I got stuck in the contest. I am not sure how to efficiently compute $f[i,j]$ by dynamic programming, although I suspect this approach can be made to work. It feels like a hell of a lot of work though, so I am curious to see if there is a more straightforward approach. I strongly believe that most solutions should leverage the claim above.

It turns out that we need to notice that we need at least $k$ time to move through $k$ cells. Any additional time is spent waiting at some cells. Observe that it makes no difference where we wait, i.e. if we wait at a cell for 2 seconds and another for 4 seconds, then we can convert it to a path where we wait 6 seconds at the first cell and move directly through all cells with no waiting. So we compute the minimum waiting time for a path instead. 

For the $k$th cell in a path at $(x,y)$, the minimum waiting time $t$, is $t\geq a_{x,y}-k$. So we can take the maximum of the minimum waiting times over all cells in the forced path as our minimum waiting time for that path. If we know the minimum waiting time for a path from cells $[i,j]$, call it $t_{[i,j]}$, then we can compute the minimum waiting time $t_{[i,j+1]}=\max(t_{[i,j]}, a_{j}-(j+1-i))$. Also $t_{[i-1,j]}=\max(t_{[i,j]}+1, a_{i-1})$. This gives us everything we need to write an $O(m)$ solution.