Skip to content
Tutorials Center
My learning

Topics

Lesson 13 of 63 ยท Ad Hoc and Implementation

Ad Hoc and Constructive Problems

Learn how to attack ad hoc and constructive contest problems: find invariants, explore small cases by brute force, guess a pattern, then build and verify an answer.

Some problems fit no named technique. There is no segment tree, no DP table, no graph in sight; the statement just asks a question and the solution is a short observation. These are called ad hoc problems (Latin for "for this purpose"). A close relative is the constructive problem, which asks you to produce an object, such as a permutation, a string or a grid, that satisfies some property, or to say that none exists.

Ad hoc problems feel like puzzles, and people often say they cannot be learned. That is only half true. You cannot memorise the answers, but you can learn a method: experiment on small cases, look for something that never changes, guess a formula and then check it with a program. This lesson teaches that method with three worked examples, and the code is what keeps you honest. The stress testing tools from earlier are your main instrument here.

The method

flowchart TD
  A["Write a brute force<br/>for tiny inputs"] --> B["Print answers for<br/>n = 1, 2, 3, ..."]
  B --> C["Look for a pattern<br/>or an invariant"]
  C --> D["State a conjecture"]
  D --> E["Check it against<br/>the brute force"]
  E -- "fails" --> C
  E -- "holds" --> F["Prove it briefly,<br/>then code the formula"]

Experiment, conjecture, verify, prove. The loop repeats until the conjecture survives the brute force.

A proof is nice, but in a contest you often settle for "it matches the brute force for every small case, and I can see why". Seeing why is important: patterns that merely match small data can still be wrong, so always try to explain the pattern in one sentence.

Invariants: what never changes

An invariant is a quantity that stays the same (or keeps some property) under every allowed move. Invariants prove that some goals are impossible and tell you which ones are reachable.

Problem: a row of n coins, each heads (0) or tails (1). One move flips two adjacent coins. Which configurations can be turned into all heads?

Before thinking, let the computer explore. A breadth-first search over all 2^n states gives the ground truth for small n. Then look at the answer.

Python Which coin rows can reach all heads?

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For every n the reachable count is exactly half of all states, and every reachable state has an even number of tails. The reason is the invariant: flipping two coins changes the number of tails by -2, 0 or +2, so its parity never changes. All heads has zero tails (even), so only even configurations can ever reach it. The search shows that parity is also sufficient (the counts are exactly half), so the answer to the problem is: possible if and only if the number of tails is even.

Typical invariants to look for are parity, the sum modulo some number, the multiset of elements, the sorted order, and a colouring (like a chessboard) that each move respects.

From small cases to a formula

Problem: you have n numbers. One move adds 1 to all numbers except one of your choice. What is the minimum number of moves to make all numbers equal?

Adding 1 to everyone except one element is the same, for the purpose of making them equal, as subtracting 1 from that one element. That changes the problem into "reduce elements by 1 until all are equal to the minimum", whose answer is sum(a) - n * min(a). If you did not spot that, the pattern would appear from the data. Compare a BFS on tiny inputs with the conjectured formula:

Python Conjecture a formula and test it against BFS

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

All inputs agree, so the conjecture survives. The explanation matches: only differences between elements matter, and each move shrinks the largest gap by exactly one. Notice how the brute force is limited by a cap (limit) to stay finite; when you write one yourself, always make sure it terminates.

When a problem lets you "add to all but one", "move a value to a neighbour" or "swap and pay a cost", try to rewrite the operation in an equivalent, simpler form. Often a hard-looking process is a simple counting question in disguise.

Constructive problems: build the answer

Problem: given n, output a permutation of 1..n in which no two neighbouring numbers differ by exactly 1, or report that none exists.

Experiment first. For n = 1 the single permutation works trivially. For n = 2 and n = 3 every permutation fails (try them). For n = 4 the arrangement 2 4 1 3 works. The idea behind it: even numbers differ from each other by at least 2, so do odd numbers, and the only dangerous spot is the junction between the two groups. Put evens first, then odds; the junction is (largest even, smallest odd). For n >= 4 we can orient it so the junction differs by more than 1.

Python Build and verify a permutation with no adjacent neighbours

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The loop compares the construction against exhaustive search for n up to 8, and then checks the construction alone on larger sizes where brute force is impossible. This two-step check is the standard way to trust a constructive solution: the brute force proves that impossible really means impossible for small n, and a validator proves that every built answer is correct for large n.

Proving by construction

For constructive problems the proof is the construction itself, plus a short argument that it always satisfies the property. For the permutation above: inside the evens block and inside the odds block neighbours differ by 2 at least, and the junction differs by more than 1 as soon as n >= 4 (try n = 4: 2 4 | 1 3 has junction 4, 1, difference 3). Write that argument in a sentence before you submit; if you cannot, your construction probably has a hole.

Common ad hoc patterns

  • Parity and modulo. Moves that change values by 2 preserve parity; moves by k preserve the residue mod k.
  • Extremes matter. The answer often depends only on the minimum, maximum or sum, not on the details between them.
  • Reduce the operation. "Increase all but one" is "decrease one"; "swap adjacent" counts inversions.
  • Think backwards. Start from the final state and undo moves; the reverse process is sometimes simpler.
  • Pigeonhole and counting. If there are more items than slots, something must repeat.
  • Greedy from one end. Fix the smallest decision first and show it never hurts; see greedy algorithms and how to trust them.

The pigeonhole principle

If you put more than k pigeons into k pigeonholes, at least one hole holds two or more pigeons. It sounds trivial, and it is one of the most useful ideas in contests, because it turns "does such a pair exist?" into a statement about sizes. The generalized form says that with n pigeons and k holes, some hole holds at least ceil(n / k) pigeons.

Everyday versions: among 13 people, two share a birth month; if a drawer holds black, white and brown socks, four socks guarantee a matching pair; among any 367 people, two share a birthday.

How to recognize a pigeonhole problem

  1. The statement asks whether something must exist ("prove that", "print YES if there always exists a pair") rather than asking you to find the best one.
  2. A constraint is suspiciously small or suspiciously large. If the answer is trivially "yes" once n is bigger than some bound, and the bound is small (n > m, n > 26, n > sqrt(limit)), a hidden pigeonhole is at work. The brute force then only needs to run for the small n.
  3. There is a natural bucket function: a remainder modulo m, a pair (x, x + 1), a value range, a prefix sum modulo something.

Method: choose the pigeons and the holes

  • Decide what the pigeons are (the objects you have: numbers, prefixes, people).
  • Decide what the holes are (the classes of things you want two pigeons to share: remainders, intervals, colors).
  • Count both. If pigeons outnumber holes, a collision is guaranteed, and the collision itself is usually the structure you were after (two equal remainders mean a difference divisible by the modulus).

Three classic uses

  • Two numbers with a difference divisible by m. Pigeons are the n numbers, holes are the m remainders. If n > m, two numbers share a remainder, so the answer is always yes. Otherwise n <= m and you can check the remainders directly.
  • A contiguous block whose sum is divisible by n. Among any n integers there is always a non-empty consecutive block with sum divisible by n. The pigeons are the n + 1 prefix sums P0 = 0, P1, ..., Pn, the holes are the n remainders mod n. Two prefixes share a remainder, and the block between them has a sum that is a multiple of n.
  • Among n + 1 numbers chosen from 1..2n, two are consecutive. Holes are the n pairs {1,2}, {3,4}, .... Two numbers in the same pair differ by one.

A famous bigger result in the same family is the Erdล‘sโ€“Szekeres theorem: any sequence of n^2 + 1 distinct numbers contains an increasing or a decreasing subsequence of length at least n + 1. Pigeonhole logic is also why the birthday paradox surprises people: with only 23 people the chance of a shared birthday already exceeds one half, because the number of pairs grows quadratically while the holes stay at 365.

Python Pigeonhole: guaranteed pairs and blocks

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Beware of the empty answer

The principle proves that a collision exists; it does not say where. To print the pair or the block, you still scan once and remember the first holder of each hole, as the code above does with first_seen. And it never helps when pigeons do not outnumber holes: then the pairs may all be distinct, and you have to search.

When you are stuck

  1. Solve n = 1, 2, 3, 4 by hand and write the answers in a row.
  2. Write the brute force and print many more terms.
  3. Plot differences between consecutive terms, or ratios. Quadratic growth has constant second differences; powers of two double.
  4. If the answer is a yes/no, print which small inputs are "yes" and look at what they share.
  5. If two minutes of thinking produce nothing, move to another problem and come back. A fresh mind often sees the invariant at once.

Related practice problems with solutions appear in the warm-up set.

Classic puzzles that keep coming back

A handful of old puzzles appear in contests again and again, usually disguised in a story. If you recognize the skeleton, the answer is a few lines. Each has a full treatment elsewhere (Josephus, Tower of Hanoi, Gray code); here is the contest-ready core.

  • Josephus. n people stand in a circle and every k-th is removed until one is left. Who survives? Simulating costs O(n k) or worse. The recurrence J(1) = 0, J(m) = (J(m - 1) + k) mod m computes the survivor (0-based) in O(n). For k = 2 there is a closed form: write n = 2^a + r with 2^a the highest power of two not above n; the survivor is 2r + 1 (1-based). In words: remove the leading bit of n, double, add one.
  • Tower of Hanoi. Moving n disks takes 2^n - 1 moves. In the optimal sequence, the disk that moves on move number m is the position of the lowest set bit of m, which is the "ruler sequence" 1, 2, 1, 3, 1, 2, 1, 4, ... So questions about the m-th move of a 60-disk tower are O(1), even though the whole sequence has 10^18 moves.
  • Gray code. A listing of all n-bit numbers where consecutive entries differ in exactly one bit. The i-th code is i ^ (i >> 1). It appears whenever you must visit all subsets while flipping one element at a time.
  • N-queens counting. Place n queens so that none attack each other and count the placements. Backtracking with three bitmasks (occupied columns and two diagonals) visits only legal prefixes, and the known counts for n = 1..8 are 1, 0, 0, 2, 10, 4, 40, 92. Counting is feasible up to n of about 14; beyond that, problems expect a table of known values or a different question.
Python Josephus, Hanoi, Gray code and N-queens in a few lines

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The first loop verifies the closed form, the recurrence and a direct simulation against each other. That three-way agreement is the habit to copy: a formula you just derived is only trusted after it matches a slow, obviously correct version on small inputs.

MEX and balanced brackets

Two more small topics appear so often that they deserve their own recipes.

MEX (minimum excluded value) of a collection is the smallest non-negative integer that is not in it. Facts to keep in mind:

  • The MEX of an array of length n is at most n, so you can store the values in a boolean array of size n + 1 and scan for the first gap in O(n).
  • As you add elements to a set, its MEX never decreases. So the MEX of every prefix is computed in O(n) overall with a pointer that only moves forward.
  • To make the MEX equal to k, the values 0..k-1 must all be present and k must be absent. If a needed value is missing you must supply it; deleting elements can only remove values, never create them.

When elements are added and removed, the pointer only works for adds, because a removal can lower the MEX. Keep two structures: a counter that says how many copies of each value are present, and a min-heap of candidate values (those that are currently absent). Each query pops from the heap while the top is present again (lazy deletion) and returns the top. A value goes back into the heap when its count drops to zero. Each add or remove costs O(log n) amortized. For a sliding window use exactly this structure, adding the new element and removing the one that leaves. If the MEX of every subarray is needed, a segment tree over values (storing the last position of each value) answers "smallest value whose last occurrence is before l" in O(log n).

Python MEX under adds, removes and sliding windows

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Balanced brackets. A sequence of ( and ) is valid when no prefix has more closing than opening brackets and the totals are equal. Track a running balance (+1 for (, -1 for )). Useful consequences:

  • A valid check is one pass: the balance never goes negative and ends at zero.
  • The minimum number of insertions to repair a string is the number of times the balance would go below zero (each fixed by an inserted () plus the final leftover balance (fixed by ) insertions).
  • A stack gives the matching partner of each bracket.
  • The number of valid sequences with n pairs is the Catalan number C(n); a DP over the balance computes it, and Lucas, Catalan and Stirling gives the formula.
Python MEX of every prefix, and bracket repairs

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Every function is compared against a brute force: all subsets for the MEX removal question, and a breadth-first search over strings for the bracket repairs. Both are exponential, which is fine because they only see tiny inputs.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is an invariant?

    An invariant is preserved by every operation. If the goal state violates it, the goal is unreachable.
  2. 2. A move flips two adjacent coins. Why can a row with an odd number of tails never become all heads?

    All heads has zero tails, which is even. Parity of the tails count is preserved by every move, so odd counts can never reach it.
  3. 3. Why compare a conjectured formula with a brute force on small cases?

    Agreement on many small cases does not prove a formula, but disagreement disproves it instantly, so it is a cheap and powerful filter.
  4. 4. How do you gain trust in a construction for large n where brute force is impossible?

    A validator is cheap even for large outputs, while exhaustive search is not. Together they cover small and large cases.

Summary

  • Ad hoc problems need an observation, not a named algorithm; constructive ones ask you to build an object or prove none exists.
  • Work from tiny cases with a brute force, then conjecture, test and explain.
  • Invariants such as parity show what can never happen and what is reachable.
  • Rewrite operations into simpler equivalents ("add to all but one" is "subtract from one").
  • Verify constructions with a validator on large sizes and with exhaustive search on small ones.
  • If stuck, collect more data instead of staring at the statement.
  • Recognize Josephus, Hanoi, Gray code and N-queens in disguise; MEX is monotone over prefixes; brackets reduce to a running balance.

Next: Simulation and Cycle Detection