vii. Observation Toolkit

“Ad hoc” means no standard algorithm applies: the solution is one or two observations that collapse the problem, then a few lines of code. The observations come from a small set of moves. This note lists them; the next notes go deeper into each family.

The loop

1. Brute force small cases ($n\le 8$) and print a table: the answer, the optimal object, or which inputs are “yes”.
2. Stare at the table: monotone? periodic? depends only on $n\mathrm{mod}k$, on parity, on the count of something? equals a simple formula (search OEIS)?
3. Guess a characterization, then try to prove it (or at least stress-test it against the brute force on random inputs).
4. Code the characterization; keep the brute force for stress testing.

// table printer: every array of length n with values in [0, k)
template<class F> void table(int n, int k, F f) {
    vector<int> a(n);
    for (long long m = 0, tot = (long long)pow(k, n); m < tot; m++) {
        long long t = m; for (int& x : a) x = t % k, t /= k;
        for (int x : a) printf("%d ", x);
        printf("-> %s\n", f(a).c_str());
    }
}

Moves that produce observations

Move	Ask	Typical payoff
Invariants	What never changes under the operation (sum, parity, xor, gcd, multiset mod $k$, inversion parity)?	impossibility, and “the answer depends only on the invariant”
Monovariants	What always increases or decreases?	termination, bounds on the number of steps
Extremes	Look at the max/min element, the first/last move, the leftmost/rightmost object.	the max must be handled first or last, so the problem peels
Reverse the process	Run the operations backwards from the target.	the backward process is often forced (greedy)
Answer is tiny	Is the answer always $\le 2$ or $\le 3$?	check 0, then 1, else the small constant
Canonical form	What is the simplest representative of all states reachable from this one?	reachability = equal canonical forms
Fix one thing	Fix the first element, the value of the answer, or the last operation.	the rest becomes forced or greedy
Contribution	Count each element’s contribution instead of each structure.	sums over all subarrays, pairs, subsets
Symmetry / normalisation	Sort, rotate, reflect, assume $a\le b$.	fewer cases

Reverse the process: a template example

Reach $n$ from $1$ with the operations $x\to x+1$ and $x\to 2x$, using as few as possible. Forward there are two choices at each step. Backward there is only one sensible choice: halve when even, otherwise subtract 1.

int minOpsFromOne(long long n) {               // walk back: halve when even, else subtract 1
    int ops = 0;
    while (n > 1) { n = (n % 2 == 0) ? n / 2 : n - 1; ops++; }
    return ops;
}

Proof: walking back greedily is optimal

Let $f(n)$ be the optimum. For odd $n>1$ the last operation must be $+1$ (doubling gives even numbers), so $f(n)=f(n-1)+1$. For even $n$, if the last step is $+1$ from $n-1$ (odd), the step before that is also $+1$ from $n-2$; but $n-2=2(n/2-1)$ and from $n/2-1$ the two steps “double, then $+1$, then $+1$” can be replaced by ”$+1$, then double”, which reaches $n$ in fewer steps. By induction, halving is never worse, so $f(n)=f(n/2)+1$ for even $n$. Tested against BFS for all $n\le 3000$.

Checklist when stuck

• Did I solve $n=1,2,3$ by hand and look at the brute-force table?
• What is invariant? What is monotone?
• What does the optimal answer look like? Can I assume it has a normal form (sorted, contiguous, at most one “special” element)?
• Can the operations be reordered freely? Does the order matter at all?
• Is the answer bounded by a tiny constant?
• Is there a reduction to a known problem (see Reduction Catalog)?

See also Attacking a Problem and Invariants and Extremal Arguments.