viii. When the Answer Is Small

Many Div. 2 A–C and some Div. 1 problems ask for “the minimum number of operations”, and the answer is always in a set like $\{0,1,2\}$ or $\{-1,0,1,2,3\}$. The method:

1. Find a universal strategy that always works in $c$ operations (often “apply the operation to the whole array” a couple of times).
2. Characterize exactly when $0,1,\dots ,c-1$ operations suffice. Each characterization is usually a simple scan.
3. Prove the lower bounds: when the cheaper checks fail, fewer operations are impossible.

The brute-force table from Observation Toolkit shows the bounded answer at once.

Example 1: sorting by rearranging proper subarrays

Operation: choose a subarray that is not the whole array and rearrange it arbitrarily. Minimum operations to sort a permutation of $\mathrm{1..}n$ ($n\ge 3$):

int permutationSort(const vector<int>& p) {    // rearrange any proper subarray; values 1..n
    int n = sz(p);
    if (is_sorted(all(p))) return 0;
    if (p[0] == 1 || p[n - 1] == n) return 1;
    if (p[0] == n && p[n - 1] == 1) return 3;
    return 2;
}

Proof: the answer is 0, 1, 2 or 3 exactly as coded

If $p_1=1$, sort $p_2..p_n$ in one operation; symmetrically if $p_n=n$. Otherwise one operation cannot work: a proper subarray misses position $1$ or position $n$, and the element there is wrong. Two operations work whenever $p_n\ne 1$: sort positions $\mathrm{1..}n-1$ (this brings $1$ to the front, because $1$ is among them), then sort positions $\mathrm{2..}n$. Symmetrically, two work whenever $p_1\ne n$. The case $p_1=n$, $p_n=1$: sorting positions $\mathrm{1..}n-1$ moves $n$ away from the front, and then two more operations finish, so three suffice. Two do not: after any first operation, $n$ is still at position $1$ or $1$ is still at position $n$; then neither $p_1=1$ nor $p_n=n$ holds, so one more operation cannot sort. Verified by BFS over all permutations for $n\le 5$.

Example 2: make everything zero with mex

Operation: choose $[l,r]$ and set every $a_i$ ($l\le i\le r$) to $\mathrm{mex}(a_l..a_r)$. Minimum operations to make the array all zeros:

int mexToZero(const vector<int>& a) {          // set a[l..r] := mex(a[l..r]); make everything 0
    int l = 0, r = sz(a) - 1;
    while (l <= r && a[l] == 0) l++;
    while (r >= l && a[r] == 0) r--;
    if (l > r) return 0;
    for (int i = l; i <= r; i++) if (a[i] == 0) return 2;
    return 1;
}

Proof: 0 if all zero, 1 if the nonzeros form one block, else 2

If the nonzero elements form one contiguous block, applying the operation to that block gives mex $0$ (no zero inside), so one operation suffices. One operation must cover every nonzero element, so its segment contains the block hull; if a zero lies inside the hull, the mex is positive and the segment becomes nonzero. Two operations always suffice: apply it to the whole array, getting a constant $m$; if $m>0$, apply it again, and the mex of an array of $m$‘s is $0$. Verified by BFS over all arrays of length $\le 5$ with values in $\{0,1,2\}$.

Where small answers hide

Signal	Universal strategy
”operation on any subarray / substring”	apply to the whole thing, or to a prefix plus a suffix
”minimum number of operations” with a $-1$ case	an invariant decides $-1$; otherwise the answer is $\le 2$ or $3$
operations with mex, gcd, or, and	applying to everything collapses the array to a constant
”make the array good” where good is a local condition	fix one end, then the other

Related: Proof Techniques.