Dadas and Mog's Binary Sequence

For a binary string $C$, consider the values $H_0(C),H_1(C),\ldots,H_N(C)$ defined in the constraints. Reading one character changes the value by exactly one.

For each $i$ ($1 \leq i \leq N$), define

$$E_i(C)=\min(H_{i-1}(C),H_i(C)).$$

The equality $E_i(C)=x$ means that the $i$-th step crosses the boundary between the integers $x$ and $x+1$.

An interval $[l,r]$ contains equally many zeroes and ones exactly when $H_{l-1}(C)=H_r(C)$. Applying an operation reverses only the order of the crossed boundaries inside this interval. Thus, it reverses $E_l(C),E_{l+1}(C),\ldots,E_r(C)$ and leaves all other values unchanged.

Therefore, for every integer $x$, the number of crossings between $x$ and $x+1$ is invariant. Hence the following two multisets must be equal:

$$\{E_1(A),E_2(A),\ldots,E_N(A)\},\qquad \{E_1(B),E_2(B),\ldots,E_N(B)\}.$$

This condition is also sufficient. Regard $E(A)$ as the current sequence and $E(B)$ as the target sequence, and make them equal from left to right.

Assume the first $i-1$ positions already match. If $E_i(A)=E_i(B)$, continue. Otherwise, the two edge levels describe the two opposite directions available from the current height. Since the current path first moves in the wrong direction, the first later crossing of the target edge leaves the current height toward the target side, and its second crossing returns to the current height.

Let $j$ be the position of the second occurrence of $E_i(B)$ in the current suffix starting at $i$. The original binary-string interval $[i,j]$ starts and ends at the same height, so it contains equally many zeroes and ones and is a valid operation interval.

The operation reverses $E_i(A),E_{i+1}(A),\ldots,E_j(A)$. Since the last value is $E_j(A)=E_i(B)$, the new value at position $i$ becomes correct.

When the invariant multisets are equal, the required second occurrence always exists. For every position, scan the remaining suffix linearly and reverse the selected segment directly. Each position costs $O(N)$ time, so the total time complexity is $O(N^2)$. The memory complexity is $O(N)$.

At most one operation is produced for each position, so the total number of operations is at most $N$.

Solution written by GPT5.6