Codeforces Round 968 Discussion stream (with hints)

Solve with $K=2$ only.

Turtle wants to maximise the remaining value, so he should try to remove the smallest values. Similarly Piggy wants to minimise the remaining value, so he should try to remove the largest values.

Try to find bad pairs.

Some of the bad substring are:

• aaaabbbbb
• aabb
• ab

Some of the good substring are:

• ababababb
• abab

Intuitively, we should try to create a string which does not contain equal chars together.

Lets pick an array $B_1,B_2,…,B_M$, and see what happens when we do operation of X, with this array. Let $\text{sm1}$ be the smallest missing value in B, and $\text{sm2}$ be the second smallest missing value in B.

Now, if $X=\text{sm1}$, $\text{mex}(\text{X}, B_1, B_2, \ldots, B_M) = \text{mex}(\text{sm1}, B_1, B_2, \ldots, B_M) = \text{sm2}$

otherwise, $\text{mex}(\text{X}, B_1, B_2, \ldots, B_M) = \text{sm1}$

Now, we can model it as a graph problem. Graph consists of $m+1$ nodes labelled with $0,1,…,m$ From any node we can reach $\text{sm1}$, and from $\text{sm1}$ we can reach $\text{sm2}$.

Our goal is to find for each node, maximum labelled we can reach starting from it.

We cannot create a graph of size $m+1 = 10^9 + 1$. Let $K=\max(\text{sm2})$ ie $K$ is maximum value of second maximum among all arrays given in input.

Notice that maximum X, we can reach after doing any operations is $K$. So for all $i>K$, we should not do any operations, and $F(i)=i$.

Now, we can directly, calculate sum of i more than $K$ and create a graph with $K+1$ nodes.

Next observation was, from $X$, we will go to smaller value only once.

Refer hints of D1.

Because we cannot use same array twice, the only difference it makes it, If from $X$ we go to $\text{sm1}$ of an array, we will not be able to go to $\text{sm2}$ with the same operation. So we should reach $\text{sm1}$ using some other array, if it exists. If such an array does not exists, we will not be able to reach $\text{sm2}$ using this operation.

First solve for case $L_1=1, R_M=N$ and $R_i + 1 = L_{i+1}$, ie every element is part of some range.

For each range lets fix $K_1,K_2,K_3,…,K_M$, and see how does an interesting permutation looks like.

Let $P_1=K_1-L_1+1$, $P_2=K_2-L_2+1$, and so on… Similary let $S_1=R_1-K_1$, $S_2=R_2-K_2$, and so on…

Let $P = \sum P_i$ and $S = \sum S_i$. Smallest $P$ elements should go to prefix of each range and largest $S$ elements should fo to suffix of each range.

In optimal permutation, we should place $1…P$ in descending order in prefixes, and we should place $P+1….P+S$ in descending order in suffixes.

Now, lets do a dp, $dp[i][\text{pLen}]$, This denotes we have processed first $i$ ranges so far, smallest pLen elements went to prefix and remaining went to suffix.

Now, we can iterate on value of $P_{i+1}$ and try to count no of new inversions that will come up.

How to handle elements not present in any range? We add them in a range of length 1, and take prefix of length 1 or suffix of length 1.

Refer to hints of E1.

Lets merge all intersecting ranges, and look at a group of ranges.

All ranges in this group will have same value of $K_i$. This $K_i$ must be more than or equal to left endpoint of all ranges. And this $K_i$ must be less than or equal to right endpoint of all ranges.