2199E: Supersequence

Research note: I checked the canonical Codeforces statement at https://codeforces.com/contest/2199/problem/E, the official Kotlin Heroes 14 tutorial page at https://codeforces.com/blog/entry/151783, and the contest status page at https://codeforces.com/contest/2199/status. The official page's solution uses exactly this block/prefix-sum idea; the explanation below is original.

A useful way to strip the problem down: a beautiful array is a shortest walk on the integer line that visits $a_1,a_2,\dots,a_n$ in order. Adjacent elements of $b$ differ by $1$ , so each move changes the current value by one.

Suppose $a_i=u$ and $a_{i+1}=v$ are matched at positions $p_i<p_{i+1}$ in $b$ .

If $u\ne v$ , then in $L=p_{i+1}-p_i$ moves, the value can change by at most $L$ , so $L\ge |u-v|$ . This bound is tight: just move monotonically from $u$ to $v$ . That gives

u, u+\operatorname{sgn}(v-u), u+2\operatorname{sgn}(v-u), \dots, v.$$ So the intermediate values are completely forced. No wiggle room, no clever detour, no magic bullshit. If $u=v$, the two occurrences must be at different positions. They cannot be adjacent, because then their difference would be $0$, not $1$. Therefore we need at least two moves: $v\to v+1\to v$ or $v\to v-1\to v$. This uses exactly one inserted element, but that inserted element is not unique. Also, do not assume $b_i$ must be positive just because $a_i$ is positive; the statement only bounds $a_i$. Define the shortest number of moves between consecutive required values as

d_i=\begin{cases} |a_i-a_{i+1}|, & a_i\ne a_{i+1},\ 2, & a_i=a_{i+1}. \end{cases}

Any valid $b$ containing $a$ has matched positions $p_1<\dots<p_n$, so

p_{i+1}-p_i\ge d_i.

Extra elements before $p_1$ or after $p_n$ are useless and can be removed, so in a minimum-length array we have $p_1=1$ and

m=1+\sum_{i=1}^{n-1} d_i.

The lower bound is achievable by concatenating the shortest bridges for every neighboring pair, overlapping endpoints. Therefore the positions of all anchors $a_i$ are fixed in every beautiful array. Now split the whole answer line into blocks: - an anchor block of length $1$ for each $a_i$; - between $a_i$ and $a_{i+1}$: - if they differ, a gap block of length $|a_i-a_{i+1}|-1$ containing the forced intermediate values; - if they are equal, a gap block of length $1$ whose value is ambiguous, so queries there answer $0$. For example, between $4$ and $1$ the forced block is $3,2$. Between $1$ and $1$ there is one ambiguous slot: it can be $0$ or $2$, so the answer is $0$. Store all block lengths and their prefix sums. For a query position $x$: 1. If $x>m$, answer $-1$. 2. Otherwise find the first prefix sum at least $x$ using binary search. That tells us which block contains $x$. 3. If it is an anchor block, output the corresponding $a_i$. 4. If it is an equal-pair gap, output $0$. 5. Otherwise it is a forced monotone gap. If the left endpoint is $u$ and the direction is $s\in\{-1,1\}$, and the offset inside the gap is $t$, output $u+s\cdot t$. Zero-length forced gaps happen when $|a_i-a_{i+1}|=1$; they are harmless. Prefix sums may repeat, but `lower_bound` still lands on the previous non-empty block for real positions. Complexity: building the blocks is $O(n)$, each query is $O(\log n)$, and memory is $O(n)$.

Supersequence

Progressive nudges

Full explanation

Generated C++