What is an ad hoc problem?
Some problems match a technique with a name, such as sorting, trying every case or a bit trick. Others match none of them. An ad hoc problem is one we solve by reasoning from its own rules until we notice a fact that gives the answer. Let's start with a small puzzle.
Three cards lie in a row, written 0 for face down and 1 for face up. One move flips two neighbouring cards. Starting from [0, 1, 1], can we make every card face up?
List every state you can reach
With no technique that fits, we study the moves themselves, and three cards are few enough that we can list every row we can reach. The state is everything that can affect later moves, here the row of three values. A move picks one of the two neighbouring pairs, and the goal is [1, 1, 1].
| State | Face-down count | How to reach it |
|---|---|---|
| [0, 1, 1] | 1 | Start |
| [1, 0, 1] | 1 | Flip the left pair |
| [0, 0, 0] | 3 | Flip the right pair |
| [1, 1, 0] | 1 | Flip each pair once |
Flipping either pair in any of these rows gives another row already in the table, so these four are all the states we can reach, and the goal is not one of them. Now let's read the face-down counts: 1, 1, 3 and 1. Every reachable state has an odd face-down count, and the goal's count, 0, is even. For now that is only a pattern in four rows. The next part proves it for a row of any length.
What can a move never change?
In the general problem, a row of cards is written as zeros and ones, and a move flips two neighbouring cards. We want the fewest moves that turn the whole row face up, or -1 if that is impossible.
Take [1, 0, 1, 1, 0, 1]. Counting positions from 0, flipping the pairs that start at positions 1, 2 and 3 turns every card up, so three moves are enough. For [0, 1, 1], the table showed that nothing works. A search like the table's may visit all arrangements of cards, and for 30 cards that is
over 10 seconds at a judge's rough simple steps a second. Instead of searching, we need two things: a test that proves a row impossible, and a rule that builds a shortest sequence when one exists.
Explore card flips and reachability
Clicking a card flips it together with its right neighbour, and the face-down count appears under the row. Before clicking, decide: can every card end face up from here? The widget answers by searching every arrangement the moves reach.
The second setting makes a move flip three cards in a row, which changes the face-down count by an odd amount, so its parity alternates and rules nothing out. The letters under the cards colour the positions A, B, C, A, B, C, A in turn: what does a three-card move do to each colour?
With two-card moves, the starting row [0, 1, 1, 1, 0, 0, 1] is stuck, because three cards are face down. With three in a row, each move flips one card of colour A, one of B and one of C, so the face-down counts of the three colours always change parity together. They start at 1, 1 and 1, so after an odd number of moves all three are even, as in the all-up row, and the search finds a way in 3 moves.
Card flips preserve the parity of the face-down count
To see why the count stays odd, look at a single move on two neighbours. Before the flip, the two cards are both up, both down, or one of each.
In every case the count changes by an even amount, so its parity, whether it is odd or even, never changes. All face up means a count of 0, which is even. So a row that starts with an odd face-down count can never be turned all face up.
Definition
An invariant is a quantity that no move changes. If the target has a different value, the target is out of reach.
An even count only tells us that parity is not the obstacle; to show the target can be reached, we still have to build the moves.
How do you prove a process stops?
An invariant tells us what a process can never reach. Some problems ask a different question: does a process end at all, and after how many steps? Take "while two neighbours are out of order, swap them". To prove that this loop stops, whichever pair we swap, we look for a quantity that moves in one direction only, called a monovariant. If it is a whole number that never goes below 0 and every step lowers it, the process must stop.
For neighbour swaps, that quantity is the number of inversions, the pairs of positions whose values are in the wrong order:
Let's count them in [4, 3, 1, 2]. The 4 comes before 3, 1 and 2, and the 3 comes before 1 and 2:
Swapping an out-of-order neighbouring pair fixes exactly that pair. Every other pair keeps its order, because any other value sits on the same side of both swapped positions. So each swap removes exactly 1 inversion, and the process stops after exactly 5 swaps, whichever out-of-order pair we pick each time.
| Swap | Array after it | Pair swapped | Inversions |
|---|---|---|---|
| Start | [4, 3, 1, 2] | none | 5 |
| 1 | [3, 4, 1, 2] | 4 and 3 | 4 |
| 2 | [3, 1, 4, 2] | 4 and 1 | 3 |
| 3 | [1, 3, 4, 2] | 3 and 1 | 2 |
| 4 | [1, 3, 2, 4] | 4 and 2 | 1 |
| 5 | [1, 2, 3, 4] | 3 and 2 | 0 |
When is a move the only one that can fix a card?
Back to the cards. The parity test tells us when to give up; when the count is even, we still need the fewest moves. Flips give the same result in any order, and making the same move twice undoes it, so a solution is just a set of pairs: each pair is flipped once or not at all.
Now let's go through the cards from the left. Card 0 is touched only by the move on cards 0 and 1, so we use that move exactly when card 0 starts face down. Once that is decided, card 1 has one undecided move left, the one on cards 1 and 2, and we use it exactly when card 1 is face down at that point. Each move in turn is forced by the card on its left.
Let's run the scan on [1, 0, 1, 1, 0, 1]. Card 0 is up, so we leave it. Card 1 is down, so we flip cards 1 and 2. That turns card 2 down, so we flip 2 and 3, which turns card 3 down, so we flip 3 and 4, and now every card is up. These are the three moves we found by hand, and since none of them was a choice, no shorter answer exists.
If the last card is still down at the end, no move is left to fix it, and by the parity rule that happens exactly when the count was odd. The figure also gives us a formula. Number the face-down positions from the left as . The scan pairs the first with the second, the third with the fourth, and so on, and each pair costs the distance between its two cards:
Implement the forced-move scan
The function copies the input, so the flips do not change the caller's list, and rejects an odd face-down count first. Then it visits positions through , fixing each face-down card with its right neighbour.
def fewest_flips(cards):
cards = list(cards)
if cards.count(0) % 2 == 1:
return -1
moves = 0
for i in range(len(cards) - 1):
if cards[i] == 0:
cards[i] = 1
cards[i + 1] ^= 1
moves += 1
return moves
print(fewest_flips([1, 0, 1, 1, 0, 1]))
print(fewest_flips([0, 1, 1]))The two rows print 3 and -1.
Setting cards[i] = 1 records the fixed card, and XOR with 1 flips the next card, whose value is 0 or 1. The last card needs no move of its own: with an even starting count, parity forces it to be up once every card before it is up. An already-up row and an empty row both return 0, and a single face-down card returns -1.
Forced-move scan invariant
When the scan reaches position , every card before is face up, and among the pairs before , the scan has flipped exactly those that every solution flips.
The scan makes exactly the forced choices, so every solution flips at least the pairs the scan flips, and the returned count is the minimum.
Worked example
Trace the forced-move scan
The trace counts the face-down cards first and stops at once if the count is odd. Otherwise it scans left to right and makes each forced move. Odd face-down count shows the impossible row, and in Two separate pairs the face-down cards pair up as 0 with 2 and 5 with 6.
U is face up and D is face down. 2 cards are face down, an even count. A move changes that count by -2, 0 or +2, so its parity never changes.
- face down
- 2
- parity
- even
Change the example input
Current result: 3
Deeper read: test a claim against a brute-force solver
Even a proved rule is worth testing, because a proof can miss a case. To test it, we keep a slow solver whose correctness is obvious and compare it with the fast one on thousands of random small rows. Here the slow solver tries every set of pairs to flip, which is enough because a solution is a set of pairs: bit of mask says whether pair is flipped.
def brute(cards):
n = len(cards)
best = -1
for mask in range(1 << max(n - 1, 0)):
row = list(cards)
for i in range(n - 1):
if (mask >> i) & 1:
row[i] ^= 1
row[i + 1] ^= 1
used = bin(mask).count("1")
if all(row) and (best == -1 or used < best):
best = used
return best
for _ in range(2000):
cards = [random.randint(0, 1) for _ in range(random.randint(1, 10))]
assert fewest_flips(cards) == brute(cards), cardsA failing assert prints the row that breaks the rule.
Ten cards give sets of pairs, so each brute-force answer is instant. The parity rule and the scan pass this test, and a run over every row of 1 to 10 cards, all 2,046 of them, finds no mismatch either. When a mismatch does appear, the failing row has at most 10 cards, few enough to solve by hand, and solving it shows what the rule missed.
Why work backwards from the target?
So far we have followed the moves forwards. Sometimes it pays to run them in reverse, from the goal back to the start: the last move into a state can be forced even when the first move out of the start is a free choice, and then a branching search becomes a straight line. Let's see this on a problem.
A broken calculator shows the integer startValue. In one operation you can multiply the number on the display by 2, or subtract 1 from it. Return the fewest operations needed to make the display show target.
Constraints
-
startValue,target
Sample 1 · Input
startValue = 2, target = 3
Output
2
Sample 2 · Input
startValue = 5, target = 8
Output
2
Sample 3 · Input
startValue = 3, target = 10
Output
3
Let's follow the third sample. From 3, we double to 6, subtract 1 to get 5, and double again to reach 10:
A forward search branches at every step, because every value has two choices. Backwards, from target, halving undoes a doubling and adding 1 undoes a subtraction, and while target is above start, each reverse step is either forced or the cheaper choice:
- An odd target cannot be the result of doubling, so its last step was a subtraction, and we add 1.
- For an even target, we halve now. Adding 1 instead would make the target odd, which forces a second addition before any halving. Adding 1 twice and then halving reaches in three reverse steps, while halving first and then adding 1 reaches the same number in two. More additions before halving only cost more.
Once target is at most start, halving would only push it further below, so the rest is additions, which are subtractions in the forward direction. From 10 every reverse step is forced, and the run reaches 3 in three steps:
def broken_calc(start, target):
ops = 0
while target > start:
if target % 2 == 0:
target //= 2
else:
target += 1
ops += 1
return ops + (start - target)
print(broken_calc(2, 3))
print(broken_calc(5, 8))
print(broken_calc(3, 10))The three samples print 2, 2 and 3.
The target can be halved only about times. An addition makes it even and leaves it above start, so the next step is a halving, and the loop runs at most about times. For targets up to ,
so the loop runs no more than 60 times.
When is a condition enough?
An invariant gives us conditions that every solvable input must meet, but an input that meets them may still be unsolvable. A condition is necessary if every solvable input satisfies it, and sufficient if every input that satisfies it is solvable. To prove that a list of necessary conditions is sufficient, we build the moves for every input that meets them all. Let's see this on a problem.
You have two coin piles with and coins. One move removes 1 coin from the left pile and 2 from the right, or 2 from the left and 1 from the right. For each test, print YES if both piles can be emptied and NO otherwise.
The first line holds the number of tests , and each of the next lines holds and .
Constraints
Sample · Input
3 2 1 2 2 3 3
Output
YES NO YES
We start with necessary conditions. Every move removes 3 coins, so the total's remainder modulo 3 never changes, and since the total must reach 0, it must start as a multiple of 3. Each move takes at most twice as many coins from one pile as from the other, so over all the moves, the coins taken from either pile add up to at most twice those taken from the other. So emptying both piles needs all three of these:
The second sample, , fails the first condition, which is why its answer is NO. To show that the three conditions are enough, we build the moves. Say moves take 1 from the left and 2 from the right, and moves take 2 from the left and 1 from the right. Both piles end empty exactly when
The three conditions make both counts whole numbers that are at least 0. The bound gives , the bound gives , and is a multiple of 3 whenever is, and likewise for . So moves of the first kind and of the second empty both piles. For , .
def can_empty(a, b):
return (a + b) % 3 == 0 and b <= 2 * a and a <= 2 * b
t = int(input())
for _ in range(t):
a, b = map(int, input().split())
print("YES" if can_empty(a, b) else "NO")On the sample, this prints YES, NO and YES.
To see the three conditions together, let's plot every pair of piles up to 9 coins. The total condition keeps every third diagonal of points, and the two bounds cut out a wedge between the lines and .
Recall Why is the total being a multiple of 3 not enough?
It is necessary but not sufficient. has a total of 6, but 1 coin on the left can cover at most 2 on the right, so fails and the piles cannot be emptied. In the plot it is the ringed hollow dot outside the wedge.
Heuristics to try when you are stuck
When no idea comes, each of these is worth a few minutes on the problem in front of us.
| Heuristic | What to try | Example |
|---|---|---|
| Small cases and brute force | Solve the smallest inputs by hand, or write a slow solver and print its answers in a row. | Listing the four rows reachable from [0, 1, 1] shows that every face-down count is odd. |
| Invariants such as parity | Find a quantity that no move changes. A target with a different value can never be reached. | A two-card flip keeps the parity of the face-down count, so [0, 1, 1] stays odd. |
| Colouring | Colour the positions so that every move touches the colours in the same way, then track one count per colour. | A three-in-a-row flip touches one card of each colour. |
| Monovariants | Find a whole number that every step lowers. It cannot fall below 0, so the process stops. | Each neighbour swap removes one inversion, so [4, 3, 1, 2] takes exactly 5 swaps. |
| The extreme element | Look at the leftmost, smallest or largest item. When it has only one way to be handled, handling it shrinks the problem. | Card 0 is touched by one move only, so that move is forced. |
| Work backwards | Run the moves in reverse from the final state, where the last step can be forced. | In Broken Calculator, an odd target cannot come from doubling. |
| The shape of an optimal answer | Ask what every optimal answer must look like, then search only among answers of that shape. | Flips commute and a repeated flip cancels, so a shortest card solution is a set of pairs: candidates instead of every sequence. |
| Necessary, then sufficient | List conditions that every solvable input meets, then build an answer for every input that meets them all. | Coin Piles: three conditions, then solving for the two move counts. |
| Restate the move | Describe a move by what it changes relative to everything else. The restated move can be simpler. | If a move adds 1 to every value but one, the differences change exactly as if that one value lost 1, so making [1, 2, 3] equal takes moves. |
| Construct, then check | Build answers for small inputs by hand, generalise the pattern, and test it with a checker on every small input. | Beautiful Arrangement II, on the Constructive algorithms page, alternates . |
| Label game positions | Mark each small position win or loss from the positions one move away, then look for the pattern in the losses. | On the Game theory page, Nim Game loses on multiples of 4, and Nim with many heaps on XOR 0. |
Compare each observation with a search
- Card parity check and scan
n steps - One count, then one pass of at most moves.
- Search over card sets
2ⁿ⁻¹ sets, each n steps - sets for 30 cards.
- Broken Calculator
about 2 · log₂(target) steps - At most 60 steps for targets up to .
- Coin Piles
one step per test - Three comparisons decide each pair of piles.
Mistakes in ad hoc reasoning
Guessing that the answer is the face-down count divided by 2.
- Where it breaks
[0, 1, 1, 1, 1, 1, 1, 1, 1, 0]has face-down cards, so the guess says1. The answer is9: each move only reaches a neighbour.- The fix
- The forced moves join each pair of face-down cards one step at a time, so a pair costs the distance between its cards, here . Count the forced moves.
Solving Broken Calculator forwards by doubling while the display is below the target.
- Where it breaks
- From 3 with target 10, doubling gives 6 and then 12, and two subtractions reach 10: four operations. The answer is 3, through , which subtracts before the last doubling.
- The fix
- Work backwards from the target, where each step is forced: add 1 to an odd target, halve an even one.
Key terms
| Term | Meaning |
|---|---|
| Invariant | A quantity no move changes. |
| Monovariant | A quantity every step moves in one direction. |
| Necessary, sufficient | Every solvable input meets a necessary condition; every input meeting a sufficient one is solvable. |