AtCoder shananigans

Here is the problem, and below is the raw transcript of my thoughts.

Obs: It is always optimal to use all $K$ moves.

intuitive proof. While we have moves left, each move can be used to improve the permutation. Either we can shorten it if all are in increasing order.

Or we can improve it if we have say 1 4 2 by deleting the 4.

we want to prioritise getting 1 in first position

Suppose $1$ has $p[1]=1$. If we shift, we are worsening our permutation.

So shifts become useless. Once the 1, or the lowest value possible is

positioned at the head, we will only use deletes.

We have some options for _ ... _ 1 _ ... _ to be improved

1. Delete the prefix.

2. Shift $1$ to the head.

3. Delete part of the suffix and then shift $1$ to head.

If we are going to shift, we should delete from the suffix first.

Otherwise we waste moves shifting values that will be deleted.

We can simulate this by shifting first without deleting, then

anything in the suffix before the shift can be deleted for free.

As long as we take this into account, we can ignore $3$ and just do $2$.

Sub-Problem: Given a permutation how to optimally improve it with

only deletes. Just delete whenever there is a decrease so for example:

1 3 2 4 we would first delete the $3$, then the $4$. We can use a stack to push values to while they increase and as soon as we see a decrease, we pop until it goes back to increase.

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.