xii. Ad Hoc on Arrays and Strings

Recurring observations about arrays and strings that turn “simulate the operations” into one scan.

Setting	Observation
binary strings, flip / reverse operations	count adjacent equal pairs or the number of runs; each operation changes it by a bounded amount
make a string alternating	compare against both targets 0101... and 1010...
rearrange into a palindrome	possible iff at most one character has odd count
remove a character to make a palindrome	two-pointer from both ends; at the first mismatch try skipping either side
MEX of subarrays	MEX of the whole array is an upper bound; subarrays containing all of $\mathrm{0..}k-1$ have MEX $\ge k$
“delete equal adjacent pairs”	stack simulation; the result is unique (like a group reduction)
prefix sums with a twist	answer queries by the parity / sign of prefix sums
periodic strings	the smallest period is $n-\pi (n-1)$ from the prefix function

Reversals to an alternating string

A binary string of even length with equally many 0s and 1s; one operation reverses any substring. The minimum number of operations to make it alternating:

int reversalsToAlternate(const string& s) {
    int z = 0, o = 0;
    for (int i = 0; i + 1 < sz(s); i++) if (s[i] == s[i + 1]) (s[i] == '0' ? z : o)++;
    return max(z, o);
}

Proof: the answer is max(#"00", #"11")

Let $z$ and $o$ be the numbers of adjacent equal pairs 00 and 11; both alternating targets have $z=o=0$. A reversal of $s[l..r]$ changes only the two boundary adjacencies $(l-1,l)$ and $(r,r+1)$, so it removes at most one 00 pair and at most one 11 pair. Hence at least $\max (z,o)$ operations are needed. Conversely, while some 00 pair exists and some 11 pair exists, a reversal between them breaks both; while only one kind exists, a single reversal still breaks one pair. So $\max (z,o)$ operations suffice. Verified by BFS over all balanced strings of length $\le 8$.

Pitfalls

• Strings with odd length, or unequal counts, make a target impossible: check the counts first.
• “Subsequence” vs “substring”: a subsequence operation is usually much more powerful (often the answer depends only on counts).
• For palindrome problems, the middle character of an odd-length string is unconstrained.

Related: Subarray Aggregates and MEX, Palindromes, Runs and Periodicity.