**Spoiler alert:** This post contains optional hints for [VOI26 — Lamu Training #02](https://codeforces.me/group/monK2RGqSO/contest/724570). Expand only the problem and hint you want to see. Hint 01 is available for Problems A–E;F. Problems B, C, D, and DF also have Hint 02.; Problem F remains TBDhas Hint 03. All hints are hidden separately.↵
↵
[cut]↵
↵
<spoiler summary="Problem A — Adjacent Chmax">↵
↵
<spoiler summary="Hint 01">↵
Focus on one value from the original permutation. The positions containing that value in the final array form one contiguous interval, possibly empty. What bounds this interval?↵
</spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary="Problem B — Erase and Insert">↵
↵
<spoiler summary="Hint 01">↵
After operations $1,\ldots,i$, view the current permutation as an interleaving of two subsequences. The processed values $1,\ldots,i$ must already appear in their relative order in $P$, because they will never move again. The untouched values $i+1,\ldots,N$ still appear in increasing relative order. At operation $i+1$, track how that value moves from the untouched subsequence to the processed one.↵
</spoiler>↵
↵
<spoiler summary="Hint 02">↵
Start from $P$ and undo the moves in the order $N,N-1,\ldots,1$. To undo the move of $x$, remove $x$ from the processed subsequence and place it before all values of the untouched subsequence $x+1,\ldots,N$, making $x$ its first element. How does the position of this first untouched element change as you continue undoing the moves?↵
</spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary="Problem C — Palindrome and Permutation">↵
↵
<spoiler summary="Hint 01">↵
Build a graph with one vertex for each value. For every mirrored pair with unequal values, add an edge between those values. Repairing that pair requires using the value at one endpoint, and each value can be used only once. How can you assign the edges to their endpoints?↵
</spoiler>↵
↵
<spoiler summary="Hint 02">↵
Consider a connected component with $v$ vertices and $e$ edges. If $e=v-1$, it is a tree: any one vertex may be left unused. If $e=v$, every vertex is needed. If $e>v$, repairing all its mirrored pairs is impossible.↵
</spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary="Problem D — Sum of Three Inversions">↵
↵
<spoiler summary="Hint 01">↵
A direct DP tracking all six possible triples and the inversion sum has roughly $O(N^7)$ states. Instead, examine how a pair of positions contributes to the sum of inversions. Each triple $(A_i,B_i,C_i)$ is one of only $3!=6$ possibilities. What does the pairwise contribution table reveal?↵
</spoiler>↵
↵
<spoiler summary="Hint 02">↵
Split the six triples into $G_0=\{123,231,312\}$ and $G_1=\{132,213,321\}$. For two positions whose triples belong to different groups, exactly one of the three coordinates contributes an inversion, regardless of their order. What does this make the total contribution between the groups?↵
</spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary="Problem E — Convex Sequence">↵
↵
<spoiler summary="Hint 01">↵
The convexity condition says that consecutive differences are nondecreasing. Fix the **leftmost** position attaining the minimum. How can the sequence on either side be built from simple changes that can be repeated independently? A basic ramp of length $r$ contributes $1+2+\cdots+r=r(r+1)/2$ to the total sum.↵
</spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary="Problem F — Sequence Domination">↵
TBD.↵
<spoiler summary="Hint 01">↵
Let $d_i=A_i-B_i$. A fixed difference $d_i$ is realized by exactly $M-|d_i|$ ordered pairs $(A_i,B_i)$. For a super-decreasing sequence $V$, define its slack $U_i=V_i-\sum_{j>i}V_j$. The $U_i$ are independent nonnegative numbers. Rewrite the dominance condition in terms of them.↵
</spoiler>↵
↵
<spoiler summary="Hint 02">↵
The coefficient of $U_k$ in $\sum_i d_iV_i$ is $c_k=d_k+d_{k-1}+2d_{k-2}+4d_{k-3}+\cdots$. Therefore, $A$ dominates $B$ exactly when every $c_k\ge0$. Can these inequalities be checked with one state while processing $d_1,d_2,\ldots$?↵
</spoiler>↵
↵
<spoiler summary="Hint 03">↵
Set $w_1=0$ and $w_{i+1}=d_i+2w_i$. The next choice is valid iff $d_i+w_i\ge0$. Since $|d_i|\le M-1$, all states $w_i\ge M-1$ can be merged. For an exact next state $t$, use $d_i=t-2w_i$; its weight $M-|d_i|$ is piecewise linear in $w_i$. Which two prefix sums make each transition $O(1)$?↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
[cut]↵
↵
<spoiler summary="Problem A — Adjacent Chmax">↵
↵
<spoiler summary="Hint 01">↵
Focus on one value from the original permutation. The positions containing that value in the final array form one contiguous interval, possibly empty. What bounds this interval?↵
</spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary="Problem B — Erase and Insert">↵
↵
<spoiler summary="Hint 01">↵
After operations $1,\ldots,i$, view the current permutation as an interleaving of two subsequences. The processed values $1,\ldots,i$ must already appear in their relative order in $P$, because they will never move again. The untouched values $i+1,\ldots,N$ still appear in increasing relative order. At operation $i+1$, track how that value moves from the untouched subsequence to the processed one.↵
</spoiler>↵
↵
<spoiler summary="Hint 02">↵
Start from $P$ and undo the moves in the order $N,N-1,\ldots,1$. To undo the move of $x$, remove $x$ from the processed subsequence and place it before all values of the untouched subsequence $x+1,\ldots,N$, making $x$ its first element. How does the position of this first untouched element change as you continue undoing the moves?↵
</spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary="Problem C — Palindrome and Permutation">↵
↵
<spoiler summary="Hint 01">↵
Build a graph with one vertex for each value. For every mirrored pair with unequal values, add an edge between those values. Repairing that pair requires using the value at one endpoint, and each value can be used only once. How can you assign the edges to their endpoints?↵
</spoiler>↵
↵
<spoiler summary="Hint 02">↵
Consider a connected component with $v$ vertices and $e$ edges. If $e=v-1$, it is a tree: any one vertex may be left unused. If $e=v$, every vertex is needed. If $e>v$, repairing all its mirrored pairs is impossible.↵
</spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary="Problem D — Sum of Three Inversions">↵
↵
<spoiler summary="Hint 01">↵
A direct DP tracking all six possible triples and the inversion sum has roughly $O(N^7)$ states. Instead, examine how a pair of positions contributes to the sum of inversions. Each triple $(A_i,B_i,C_i)$ is one of only $3!=6$ possibilities. What does the pairwise contribution table reveal?↵
</spoiler>↵
↵
<spoiler summary="Hint 02">↵
Split the six triples into $G_0=\{123,231,312\}$ and $G_1=\{132,213,321\}$. For two positions whose triples belong to different groups, exactly one of the three coordinates contributes an inversion, regardless of their order. What does this make the total contribution between the groups?↵
</spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary="Problem E — Convex Sequence">↵
↵
<spoiler summary="Hint 01">↵
The convexity condition says that consecutive differences are nondecreasing. Fix the **leftmost** position attaining the minimum. How can the sequence on either side be built from simple changes that can be repeated independently? A basic ramp of length $r$ contributes $1+2+\cdots+r=r(r+1)/2$ to the total sum.↵
</spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary="Problem F — Sequence Domination">↵
<spoiler summary="Hint 01">↵
Let $d_i=A_i-B_i$. A fixed difference $d_i$ is realized by exactly $M-|d_i|$ ordered pairs $(A_i,B_i)$. For a super-decreasing sequence $V$, define its slack $U_i=V_i-\sum_{j>i}V_j$. The $U_i$ are independent nonnegative numbers. Rewrite the dominance condition in terms of them.↵
</spoiler>↵
↵
<spoiler summary="Hint 02">↵
The coefficient of $U_k$ in $\sum_i d_iV_i$ is $c_k=d_k+d_{k-1}+2d_{k-2}+4d_{k-3}+\cdots$. Therefore, $A$ dominates $B$ exactly when every $c_k\ge0$. Can these inequalities be checked with one state while processing $d_1,d_2,\ldots$?↵
</spoiler>↵
↵
<spoiler summary="Hint 03">↵
Set $w_1=0$ and $w_{i+1}=d_i+2w_i$. The next choice is valid iff $d_i+w_i\ge0$. Since $|d_i|\le M-1$, all states $w_i\ge M-1$ can be merged. For an exact next state $t$, use $d_i=t-2w_i$; its weight $M-|d_i|$ is piecewise linear in $w_i$. Which two prefix sums make each transition $O(1)$?↵
</spoiler>↵
↵
</spoiler>↵
↵
