Mathematical insight

Some problems look like they demand simulation: follow the rules step by step until you land on an answer. Often you can skip the simulation entirely. Find a quantity that the rules cannot change, and you can answer the question with a single computation instead of a loop.

An invariantinvariantA property or quantity that remains unchanged through a series of operations or transformations.In the glossary is a quantity that stays the same no matter which allowed operation you apply. If a problem asks whether you can reach a target state, and you can find an invariant that differs between the start and the target, the answer is no before you write a single line of search code.

Parity as an invariant

Parity is whether a number is even or odd, and it is the simplest invariant to check.

Picture a game on a checkerboard. You start on the top-left square and want to reach the bottom-right square, moving one square at a time, up, down, left or right. Can you get there in exactly 15 moves?

Every move changes the color of the square you are standing on. Start on white, move to black, move to white, and so on. After an odd number of moves you are on the opposite color from where you started; after an even number, you are back on the starting color.

Number the squares by row and column, both starting at 0, and color a square by (row + column) % 2. The top-left square is (0, 0), color 0. On an 8-by-8 board the bottom-right square is (7, 7), and (7 + 7) % 2 is 0. The two corners are the same color. Reaching one from the other needs an even number of moves. Fifteen is odd, so the answer is no, no matter which path you try.

1import sys2
3
4def main() -> None:5    input_data = sys.stdin.read().split()6    if not input_data:7        return8
9    # Parse input: start square as (row, col), end square, and moves10    start_r, start_c = int(input_data[0]), int(input_data[1])11    end_r, end_c = int(input_data[2]), int(input_data[3])12    moves = int(input_data[4])13
14    # Color of a square: (row + col) % 215    start_color = (start_r + start_c) % 216    end_color = (end_r + end_c) % 217
18    # After an odd number of moves, color flips. After even, it stays.19    final_color = (start_color + moves) % 220
21    if final_color == end_color:22        sys.stdout.write("yes\n")23    else:24        sys.stdout.write("no\n")25
26
27if __name__ == "__main__":28    main()

0 0 7 7 15

no

The program does exactly this check: it computes each square's color from its coordinates, adds the move count to the start color, and compares the result to the target color. No path is ever explored.

A quantity that only moves one way

Not every useful quantity stays fixed. Some only move in one direction, and that is just as powerful for answering "can this process finish?"

Suppose you have a sequence of numbers and an operation that swaps two adjacent numbers whenever the left one is bigger than the right one. Can repeating this operation always sort the sequence?

Count the inversions: pairs where a bigger number sits before a smaller one. Each swap fixes exactly one inversion, so the count drops by exactly one every time. It never increases, and there are only finitely many inversions to begin with. So the process must reach zero inversions, which means the sequence is sorted. You do not need to trace the swaps to know the process finishes.

This is different from parity. Parity does not change; the inversion count does change, but only downward. Both let you answer a reachability question without a full simulation.

Closed-form solutions

Some problems ask for a quantity that depends on the input in a way you can write as a formula, not a loop.

Take a classic example: how many ways are there to tile a 2-by-n board using 1-by-2 dominoes? A straightforward solution builds up the count width by width, using the counts for smaller widths. Once you notice that this recurrence is the Fibonacci sequence, you can compute the n-th term with matrix exponentiation in O(log n) time, instead of building up all n values.

The sum of the first N positive integers gives a smaller example of the same idea. You could loop and add N numbers, or use N * (N + 1) / 2 directly. For large N, the formula is the only version that finishes instantly.

Invariants modulo k

Parity is a special case of a broader idea: a quantity taken modulo some fixed number k can stay constant even while the quantity itself changes. Suppose a token sits on a number line, and each move adds either 3 or 5 to its position. Starting at 0, can the token ever land exactly on 7?

Every move changes the position by 3 or 5, and both of those are not multiples of a common factor that divides the target, so parity alone will not settle this one; but the position modulo the greatest common divisor of the two move sizes, 1, is no restriction at all. Try a different modulus instead: track the position modulo 2. A move of 3 flips it, a move of 5 also flips it, so the position's parity flips on every move, exactly as in the checkerboard problem. Starting at 0 (even), after an odd number of moves the token sits on an odd number, and 7 is odd, so a path with an odd move count is not ruled out by parity. Here the invariant only narrows the search; it does not decide the answer on its own, and you would still need to check that some combination of 3s and 5s actually sums to 7. (Two moves of 3 and one of 5, for instance: 3 + 3 + 5 = 11. Try one 3 and one 5: 3 + 5 = 8. In fact no combination reaches exactly 7, since the smallest reachable total, other than 0, is 3.) The lesson is not that modular arithmetic always finishes the proof by itself. It narrows the possibilities and tells you which cases still need checking, which is often the difference between an approach that terminates and one that does not.

Looking for the shortcut

Before you simulate, ask what stays the same and what only moves one way. Parity, a sum, a product, a remainder modulo some number, and the relative order of elements are the usual places an invariant hides. If you can show that one of these differs between the start and the goal, the goal is unreachable, and you are done.

If the problem instead asks for a count or a total, compute it for a few small cases by hand and look at how the numbers grow. A sequence you recognize, such as Fibonacci or the triangular numbers, usually points to a formula that replaces the whole loop.

A parity check or a formula runs in one line. A simulation of the same question can take seconds on a small case and time out on a large one. Look for the invariant before you write the search.