Codeforces: The third problem

I couldn't take part in the round today because I was playing tennis =) . Anyway problem C had 2500 solves so I thought I would give it a go.

We are given a permutation of the numbers from $0$ to $n-1$ and are asked to find the number of permutations $b$, from $1$ to $n$ such that for every $1\leq l<r\leq n$, MEX$(a_l, ..., a_r)=$MEX$(b_l,...,b_r)$. Here the MEX of a sequence of numbers is the smallest non-negative number not in the sequence.

So we first observe that any sub-array which includes $0$ in $a$ must also include $0$ in $b$. Therefore, the position of $0$ in $b$ is the same as its position in $a$. Similarly, the position of $1$ is the same in both $a$ and $b$ since if it changes some sub-array whose MEX was $1$ will now be $>1$ or some sub-array whose MEX was $>1$ will now be $1$. This lead me to the following observation.

We want to make sure that all sub-arrays with MEX$=0,1,2,...,n-1$ keep their MEX unchanged. For MEX=0, this means the $0$ staying in the same position. For MEX$=1$, the same. Now for MEX$=2$, we observe that these sub-arrays must contain $0$ and $1$. Let pos$[i]$ be the position of $i$ in $a$. Then we have two cases.

Case 1: $\min(\text{pos}[0],\text{pos}[1])<\text{pos}[2]<\max(\text{pos}[0],\text{pos}[1])$.

Then the exact position of $2$, so long as it remains in this range, does not change MEX$=2$ intervals. This is because for a MEX of $2$, we need to include both $0$ and $1$ and so moving the $2$ around will not change the MEX of intervals which do not include either $0$ or $1$ in this case.

Case 2: $\min(\text{pos}[0],\text{pos}[1])>\text{pos}[2]$ or $\text{pos}[2]>\max(\text{pos}[0],\text{pos}[1])$.

Then $2$ cannot be moved at all in $b$.

In general for any $i$, we let $l=\min(\text{pos}[0],...,\text{pos}[i-1])$ and $r=\max(\text{pos}[0],...,\text{pos}[i-1])$. Then for case 1 we need $l<\text{pos}[i]<r$. 

So now we can easily find if an $i$ can be moved, and a rough range of positions it must stay within (namely $(l,r)$) . However, we need to figure out for each $i$, how many positions it can be moved to, i.e. how many elements it can swap with in $a$. Note that this will result in double counting, so we only consider for each $i$, the number of elements $>i$ that it can swap with.

If we have case 2 for some $i$, then the number of elements it can swap with is $0$. If we have case 1, then we have $r-l+1$ elements in the range $[l,r]$ of which $i$ of them are $<i$. The remaining $r-l-1-i$ elements are larger than $i$ and can be swapped with $i$ safely. Therefore, we can multiply our answer by $r-l+1-i$ every time we enter case 1.

This leads to an $O(n)$ solution basically using a two pointers method with $l$ and $r$ to maintain the range. Quite a nice problem! For me the hardest part was figuring out the correct approach to count the number of elements each $i$ can swap with.