Ad Hoc Problems

intermediate20 min

What makes a problem ad hoc

Most problems fit a category. You read the statement, recognize the shape, and apply the technique. Ad hoc problems do not fit — they turn on a specific observation about that particular setup, and once you see it the code is short.

They are frustrating because there is no technique to study. But there is a process, and it works often enough to be worth following deliberately rather than staring and hoping.

The process

When nothing standard applies

Work small cases by hand. N = 1, 2, 3, 4. Write down the answer for each. This is the highest-yield step and the one most often skipped.
Look for a pattern in those answers. Do they follow a formula? Do they depend only on some summary of the input, like its parity or its maximum?
Ask what is invariant. Is there a quantity that never changes, no matter which moves are made? Invariants often decide reachability questions immediately.
Ask what the constraints imply. A very small bound suggests brute force. A suspiciously large one suggests a formula. A bound like “N ≤ 3” means casework.
Try the extremes. All values equal, all distinct, sorted, reversed. Extremes often reveal the governing rule.
Consider working backwards from the goal state instead of forwards from the start.

Small cases

Given N, print the minimum number of moves to turn a row of N coins all heads-up, where one move flips any two adjacent coins, starting from all tails.

Do the small cases:

N	Answer	Why
1	impossible	One coin cannot be flipped alone
2	1	Flip the pair
3	impossible	Each move changes the count of heads by an even amount
4	2	Flip positions 1–2, then 3–4
5	impossible	Same parity reason
6	3	Three disjoint pairs

The pattern is immediate: possible only when N is even, and the answer is N/2. The invariant is that each move changes the number of heads by 0 or 2, so the parity of the head count never changes — and going from 0 heads to N heads requires N to be even.

if (n % 2 != 0) {
    System.out.println(-1);
} else {
    System.out.println(n / 2);
}

Two lines of code, and the entire problem was the observation.

Invariants

An invariant is a quantity unchanged by every allowed move. They are the sharpest tool for “is this state reachable” questions, because if the start and target disagree on an invariant, the answer is no with no search required.

Invariants worth checking

Parity of a count, a sum, or a position. The most common by far.
Sum or sum modulo k of all values.
Multiset of values, when moves only rearrange.
Difference between two quantities.
Colour of a square, in problems about moving on a checkerboard pattern.

The classic instance: a knight on a chessboard alternates square colour with every move, so the number of moves between two squares always has a fixed parity determined by their colours. That rules out half the candidate answers before any search.

Working backwards

Some processes are much easier to reverse.

Starting from 1, each step either doubles the current value or adds 1. Find the fewest steps to reach N.

Forwards, each state branches two ways and the search grows exponentially. Backwards from N, the move is forced: if N is even it must have come from halving, and if odd it must have come from subtracting 1.

int steps = 0;
long v = n;
while (v > 1) {
    if (v % 2 == 0) v /= 2;
    else v -= 1;
    steps++;
}
System.out.println(steps);

The exponential search becomes O(log N) because reversing removed the choice.

Reading the constraints as a hint

What an unusual bound is telling you

Constraint	Likely intent
N ≤ 3, or a fixed tiny size	Casework — enumerate the situations
N ≤ 10	Permutations, or full recursive search
N ≤ 20	Subset enumeration with bitmasks
N ≤ 10¹⁸	A closed-form formula, or O(log N) math
Answer is yes/no	Look for an invariant
Sum of N over all test cases is bounded	Per-case cost must be near-linear

The fourth row is the strongest signal in the table. If N can be 10¹⁸, no loop over N is possible, so the answer must be computable directly. That narrows the search for an approach considerably.

When you find the observation

Verify it before committing. An observation that fits N = 1 through 4 and fails at N = 7 costs more time than one you tested properly.

Verifying an observation

Test it against every hand-computed small case, including the ones you worked out before forming the hypothesis.
Test the boundary values of the constraints.
If a brute force is easy to write, stress test the formula against it. This is the most reliable check — see Debugging Under Time Pressure.
Ask whether the sample cases in the statement are consistent with it. Problem setters often include a sample specifically to rule out the common wrong guess.

If you are stuck

Ad hoc problems reward moving on and returning. If twenty minutes of hand-working small cases has produced nothing, switch problems. The observation frequently arrives while you are working on something else.

In a contest, a partial solution banked is worth more than a full solution not found. If a brute force scores points on the small test cases, submit it and come back.

Practice

For each, compute N = 1 through 5 by hand before writing any code.

Given N, print the minimum number of moves to make all of N lamps on, where one move toggles a lamp and both its neighbours in a circle.
Two players alternately take 1 or 2 stones from a pile of N. The player taking the last stone wins. Print who wins with optimal play.
Given a permutation of 1..N, print the minimum number of swaps of any two elements needed to sort it.
Given N, print whether it is possible to write N as a sum of distinct positive integers each at least 2.
A cow starts at 0 and must reach position X, where each jump is exactly 1, 2, or 3 units forward. Print the number of distinct jump sequences, modulo 10⁹+7.

Hints

Compute the small cases. The answer depends on N modulo 3 — work out why by tracking which lamps each move affects.
Compute the winner for N = 1 through 6. The pattern is periodic in N modulo 3. The losing positions are the ones where every move hands the opponent a winning position.
Not a search. Decompose the permutation into cycles; a cycle of length k needs k - 1 swaps. The answer is N minus the number of cycles.
Small cases: 1 and 2 and 3 are special. From 5 upward it is always possible. Find the exact set of impossible values by hand.
This is a recurrence, not an observation — f(x) = f(x-1) + f(x-2) + f(x-3). It is included to show that “no standard technique applies” is sometimes the wrong conclusion. See Introduction to DP.

Problem Solving Framework