xviii. Invariant-Based Constructions

The standard shape of a “-1 or construct” problem: an invariant gives a necessary condition, and a construction shows the condition is also sufficient. Find the invariant by asking what one operation preserves; find the construction by making the problem smaller (fix one position for good per operation).

Operation	Invariant	Construction idea
set $a_i,a_j,a_k$ to $a_i\oplus a_j\oplus a_k$	total xor when $n$ is even	sweep forward with $(1,2,3),(3,4,5),\dots$, then backward
add $1$ to two adjacent elements	alternating sum	fix positions left to right
swap two elements, cost by distance	multiset	cycle decomposition
flip a row or a column of a binary matrix	$a_{ij}\oplus a_{i1}\oplus a_{1j}\oplus a_{11}$	decide the first row and column, the rest is forced
choose $i$, $a_i-=1$, $a_{i+1}-=2$	weighted sums	process from the left, forced counts

Equalize by triple xor

Operation: pick distinct $i,j,k$ and set all three to $a_i\oplus a_j\oplus a_k$. Make all elements equal in at most $n$ operations, or report impossible.

vector<array<int, 3>> equalizeByXor(vector<int> a) {  // op (i,j,k): all three := a_i ^ a_j ^ a_k; at most n ops; {{-1,-1,-1}} if impossible
    int n = sz(a); vector<array<int, 3>> ops;
    if (n % 2 == 0) {
        int x = 0; for (int v : a) x ^= v;
        if (x) return {{-1, -1, -1}};
        n--;                                   // solve the first n-1; the last equals their common value (xor 0)
    }
    for (int i = 0; i + 2 < n; i += 2) ops.push_back({i, i + 1, i + 2});
    for (int i = n - 5; i >= 0; i -= 2) ops.push_back({i, i + 1, i + 2});
    return ops;
}

Proof: possible iff n is odd or the total xor is 0

Invariant. After the operation the three positions hold $y=a_i\oplus a_j\oplus a_k$ each, whose xor is $y\oplus y\oplus y=y$, the same as before; so the total xor never changes. If $n$ is even and all elements end equal to $v$, the total xor is $0$. Construction for odd $n$. The forward pass $(0,1,2),(2,3,4),\dots ,(n-3,n-2,n-1)$ makes the last position and every even position from the second operation onward carry the running xor; after it, positions $n-3,n-2,n-1$ equal the total xor $X$, and every pair $(i,i+1)$ for even $i<n-3$ is equal. The backward pass $(n-5,n-4,n-3),\dots ,(0,1,2)$ sets each triple to $u\oplus u\oplus X=X$, where $u$ is the common value of the pair. So all elements become $X$, using $(n-1)/2+(n-3)/2=n-2$ operations. Even $n$ with total xor $0$: solve the first $n-1$ elements (odd count); they all become their xor, which equals $a_n$ because the total xor is $0$. Tested on random arrays with $n\le 11$, including the operation count.

Related: Parity and Coloring, Invariants.