Informatics olympiad roadmap.

School binary search finds a value in a sorted list. Olympiads use the same halving idea on the answer. Suppose the task asks for the largest $d$ such that something is possible. Write a function ok(d) that checks one value. If ok is monotone, true for every $d$ up to the answer and false above it, you can binary search for the boundary.

This turns "find the best" into "check a guess", which is usually a simple greedy pass. The cost is $O(\log R)$ calls of ok, where $R$ is the range of possible answers: about 30 calls for $R = 10^9$, about 60 for $R = 10^{18}$.

A template for the largest true value, assuming ok(lo) is true:

def largest_true(lo, hi, ok):
    while lo < hi:
        mid = (lo + hi + 1) // 2    # round up, or the loop can stall
        if ok(mid):
            lo = mid
        else:
            hi = mid - 1
    return lo

Three things to check every time: why ok is monotone (say it in one sentence), what the starting lo and hi are, and whether you want the largest true or the smallest true value. For the smallest true value use mid = (lo + hi) // 2, set hi = mid when true and lo = mid + 1 when false.

Many tasks ask about blocks of consecutive items, such as the longest block with total at most $S$. There are about $\frac{n^2}{2}$ blocks, too many for $n = 10^5$. The two-pointer (sliding window) idea keeps a block from left to right and moves both ends only forwards.

It works when the condition is monotone in the block: if a block is good, every shorter block inside it is also good. With all values positive, a block with total at most $S$ stays good when you shrink it. So:

1. Move right one step and add the new item.
2. While the block is bad, remove the item at left and move left on.
3. Now the block is the longest good block ending at right; record what you need.

Each pointer moves at most $n$ times, so the whole pass is $O(n)$ even though there is a loop inside a loop. Counting is just as easy: the number of good blocks ending at right is right - left + 1.

If values can be negative, shrinking a block can make its total larger, the condition is no longer monotone and the method breaks. Then use prefix sums with a dictionary or a sorted structure instead.

A greedy algorithm builds the answer one step at a time, always taking the choice that looks best now, and never goes back. It is usually a sort followed by one pass, so $O(n \log n)$.

The danger is that a natural rule can be wrong. Before you code a greedy rule:

1. Try to break it with tiny examples (two or three items). If you find a counterexample, drop the rule.
2. If it survives, give an exchange argument: take any best answer that disagrees with your greedy choice, swap in the greedy choice, and show the result is no worse. Then a best answer exists that agrees with greedy at every step.
3. Still unsure? Compare it with a brute force on random small tests.

Classic correct rules: for the most non-overlapping bookings, take the one that ends first; to minimise total waiting time, serve the shortest job first; to cover points with fewest intervals, extend as far right as possible. Classic wrong rule: paying an amount with the fewest coins by always taking the largest coin works for usual currencies but not for every coin set, which is a sign the task wants dynamic programming.

For values $a_1, \dots, a_n$ define $P_0 = 0$ and $P_i = P_{i-1} + a_i$. Then the sum of a block is one subtraction:

Building $P$ costs $O(n)$, then every query is $O(1)$, instead of $O(n)$ each.

Three extensions come up all the time:

• Counting blocks. A block has sum 0 exactly when two prefix sums are equal. More generally, a block sum is divisible by $K$ when $P_r \equiv P_{l-1} \pmod K$. Count how often each prefix value appears in a dictionary; a value seen $c$ times gives $\frac{c(c-1)}{2}$ blocks.
• 2D prefix sums. For a grid, $S_{i,j}$ is the sum of the rectangle from the top-left corner to $(i, j)$, with $S_{i,j} = a_{i,j} + S_{i-1,j} + S_{i,j-1} - S_{i-1,j-1}$. Any rectangle sum is then four lookups.
• Difference arrays. To add $v$ to every item from $l$ to $r$, add $v$ at $l$ and subtract it at $r + 1$ in a difference array; one prefix sum at the end applies all the updates.

Backtracking builds a candidate one choice at a time with recursion. After each choice it checks whether the partial candidate can still be completed. If not, it abandons that branch at once (prunes) and undoes the last choice.

The shape is always the same: a recursive function place(k) that tries every option for step $k$, skips options that break a rule, makes the choice, calls place(k + 1) and then undoes the choice.

Pruning is where the speed comes from. Good pruning checks are cheap (keep sets or boolean arrays of what is used, rather than rescanning) and early (reject a bad choice as soon as it is made). For optimisation, also stop a branch when even the best possible completion cannot beat the best answer found so far.

Watch the cost of copying: pass indices and change shared lists in place, then undo, rather than building new lists at each call.

Dynamic programming (DP) solves a problem by solving smaller versions of it, storing each answer so it is worked out once. You need four things, and it helps to write them down before coding:

1. State: what $dp_i$ means, in one exact sentence, such as "the best total using the first $i$ items".
2. Recurrence: how $dp_i$ follows from smaller states, usually by asking what happens to the last item.
3. Base cases: the smallest states, filled in directly.
4. Order: fill states so that everything a state needs is already known.

The cost is (number of states) times (work per state). If you see a recursive brute force that solves the same subproblem again and again, storing answers (memoisation) turns it into DP.

In Python, filling a list with a loop is usually faster and safer than a memoised recursive function, which can hit the recursion limit. Common 1D patterns: counting ways (add the options), best value (take the max of the options), and longest increasing subsequence, where $dp_i$ is the longest run ending at item $i$.

When one index is not enough to describe a subproblem, use two. The state $dp_{i,j}$ might mean "using the first $i$ items with capacity $j$", "the cell in row $i$, column $j$" or "the first $i$ letters of one word and the first $j$ of another".

Three classics to know:

• Grid paths (moves right or down): $dp_{i,j} = dp_{i-1,j} + dp_{i,j-1}$, with blocked cells set to 0.
• 0/1 knapsack: $dp_{i,c} = \max(dp_{i-1,c},\ dp_{i-1,c-w_i} + v_i)$. You can keep one row and loop the capacity downwards, so each item is used at most once.
• Longest common subsequence of strings $s$ and $t$: if $s_i = t_j$ then $dp_{i,j} = dp_{i-1,j-1} + 1$, otherwise $\max(dp_{i-1,j},\ dp_{i,j-1})$.

The table has (rows) times (columns) entries, so check the memory as well as the time: $5000 \times 5000$ Python integers do not fit, but keeping only the previous row usually does. As in 1D, decide the order of filling first: row by row works for grids and strings, item by item for knapsack.

Root the tree at any vertex. Each vertex $v$ gets one or more DP values that describe the best answer inside the subtree of $v$, often split by a small choice about $v$ itself (taken or not, coloured or not). A vertex's values are combined from its children's values, so children must be done before parents.

In Python, a recursive DFS on a tree with $2 \times 10^5$ vertices in a line will hit the recursion limit or crash. Use an iterative order instead:

1. Do a BFS or stack walk from the root, recording each vertex's parent and the order you visit them.
2. Go through that order backwards: every child then comes before its parent.

Each vertex is handled once and each edge twice, so the whole DP is $O(n)$. Typical states: maximum weight set with no two linked vertices (two values per vertex), smallest set covering every edge (two values), subtree sizes, and the longest path through a vertex.

A subset of $n$ items can be stored as one integer mask from $0$ to $2^n - 1$: bit $i$ is 1 when item $i$ is in the set. The key operations are:

• mask >> i & 1: is item $i$ in the set?
• mask | (1 << i): add item $i$.
• bin(mask).count('1'): the size of the set.

Bitmask DP uses the subset as (part of) the state. In an assignment task, $dp[\text{mask}]$ is the cheapest way to give the jobs in mask to the first $k$ workers, where $k$ is the size of mask. In the travelling salesman problem, $dp[\text{mask}][v]$ is the shortest route that visits exactly the cities in mask and ends at $v$.

The cost is $2^n$ states times the work for each, so $O(2^n \cdot n)$ or $O(2^n \cdot n^2)$. That is why the limit is usually $n \le 20$ or less, much smaller than for other tasks. The limit itself is your clue: a small $n$ with an exponential feel means bitmask DP.

Breadth-first search (BFS) explores a graph in layers: first the start, then everything one edge away, then everything two edges away, and so on. Because it uses a queue (first in, first out), the first time it reaches a vertex is by a shortest path, when every edge counts as one move.

Store the graph as an adjacency list: adj[u] is the list of neighbours of $u$. A grid needs no list; the neighbours of a cell are the four cells next to it that are inside the grid and not walls.

BFS visits each vertex once and looks along each edge once or twice, so it is $O(V + E)$. In Python use collections.deque; popping from the front of an ordinary list is slow.

A powerful trick is the state graph. If the moves depend on more than your position (you carry a key, you have used a hammer, you have $k$ vouchers left), make each vertex a pair (position, extra information) and run BFS on those pairs. The graph is bigger, but the method is the same.

A disjoint set union (DSU, or union-find) keeps items in groups. Each group is a tree with a chosen root, and parent[x] points towards that root. Two operations:

• find(x): follow parents to the root. Two items are in the same group exactly when they have the same root.
• union(a, b): find both roots; if they differ, point one root at the other.

Two small tricks make it very fast: path compression (after a find, point every item on the path straight at the root) and union by size (hang the smaller tree under the larger). Together each operation costs almost $O(1)$ in practice.

Union-find can only join groups, never split them. When a task removes edges over time, look at it backwards: process the events in reverse, so removals become additions. This offline trick turns many hard-looking tasks into simple DSU tasks. DSU is also the heart of Kruskal's minimum spanning tree algorithm.

A spanning tree of a connected graph with $V$ vertices uses $V - 1$ edges to join every vertex with no cycle. A minimum spanning tree (MST) has the smallest total edge cost.

Kruskal's algorithm is a greedy method that is provably correct:

1. Sort the edges from cheapest to dearest.
2. Go through them in order. Take an edge if its two ends are in different groups (check with union-find), and join the groups. Otherwise skip it, because it would close a cycle.
3. Stop after $V - 1$ edges.

The cost is $O(E \log E)$ for the sort; the union-find part is almost free. The reason it works is the cut property: for any split of the vertices into two sides, the cheapest edge crossing the split belongs to some MST.

Olympiad twists include the most expensive edge on the MST (to minimise the largest single cost), counting how many groups remain after adding edges up to some cost, and Prim's algorithm, a heap-based alternative that is better for dense graphs.

A directed graph with an edge $u \to v$ for "$u$ must come before $v$" can be put in an order that respects every edge exactly when it has no directed cycle. Such a graph is a DAG (directed acyclic graph) and the order is a topological order.

Kahn's algorithm builds the order:

1. Count each vertex's in-degree (the number of edges coming in).
2. Put every vertex with in-degree 0 in a queue.
3. Repeatedly take a vertex from the queue, add it to the order, and remove its outgoing edges by lowering its neighbours' in-degrees; any neighbour that reaches 0 joins the queue.

If the order ends up with fewer than $V$ vertices, the rest lie on or behind a cycle, so no valid order exists. The cost is $O(V + E)$.

Topological order is also the order to fill a DP on a DAG: longest path, number of paths or the earliest finish time of a project all follow by going through the vertices in that order.

A priority queue supports three operations: add an item, look at the smallest, and remove the smallest. A sorted list makes adding slow; an unsorted list makes finding the smallest slow. A binary heap does both in $O(\log n)$.

A heap is a complete binary tree stored in a list, where every parent is no larger than its children, so the smallest item sits at index 0. In Python use the heapq module on an ordinary list:

• heapq.heappush(h, x) adds $x$.
• heapq.heappop(h) removes and returns the smallest.
• h[0] is the smallest, without removing it.
• heapq.heapify(h) turns a list into a heap in $O(n)$.

For the largest item instead, push $-x$ and negate when you pop. Push tuples such as (cost, vertex) to order by the first entry. Heaps appear inside Dijkstra and Prim, in scheduling simulations (which event happens next?), in keeping the $k$ largest values seen so far, and in greedy tasks that repeatedly combine the two smallest items.

Prefix sums answer range sums in $O(1)$ but one change to the array forces an $O(n)$ rebuild. A Fenwick tree (binary indexed tree, BIT) is a list t where each entry stores the sum of a block of the array whose length is a power of 2, chosen from the binary form of its index.

The block length at index $i$ is the lowest set bit of $i$, written i & -i in Python. For example 12 is 1100 in binary, so t[12] holds 4 values: positions 9 to 12.

• Add $v$ at position $i$: add $v$ to t[i], then move to i += i & -i, until past $n$.
• Prefix sum of positions 1 to $i$: add t[i], then move to i -= i & -i, until 0.

Both loops run at most about $\log_2 n$ times. The range sum from $l$ to $r$ is prefix(r) - prefix(l - 1). Positions start at 1; index 0 is unused.

Fenwick trees are short to write and fast in Python. Beyond sums they count inversions, count how many earlier values are smaller (after coordinate compression), and give an $O(n \log n)$ longest increasing subsequence with a prefix maximum instead of a prefix sum.

A segment tree is a binary tree over the array. Each leaf holds one value; each inner node holds the combined value (sum, minimum, maximum, gcd) of the range below it. A query for any range is split into at most about $2\log_2 n$ nodes, and an update changes one leaf and the $\log_2 n$ nodes above it.

The simplest version for contests is iterative and stores the tree in a list of size $2n$:

• Leaves are at indices $n$ to $2n - 1$; node $i$ has children $2i$ and $2i + 1$.
• Build: for $i$ from $n - 1$ down to 1, combine the two children.
• Update: set the leaf, then walk up to the root, recombining.
• Query $[l, r)$: start both ends at the leaves and move up, taking in a node whenever it lies at the edge of the range.

Any operation that is associative works, such as $+$, min, max or gcd. Harder versions add lazy propagation so that a whole range can be updated at once; learn that after the basic version feels easy.

Greatest common divisor. Euclid's algorithm uses $\gcd(a, b) = \gcd(b, a \bmod b)$ and $\gcd(a, 0) = a$. It takes $O(\log \min(a, b))$ steps, so it is instant even for $10^{18}$. Python has math.gcd. Then $\text{lcm}(a, b) = \frac{a}{\gcd(a, b)} \times b$; dividing first keeps numbers small in languages that overflow.

Counting multiples. The numbers from 1 to $x$ divisible by $p$ number $\lfloor x / p \rfloor$. For "divisible by $p$ or $q$" use inclusion-exclusion: $\lfloor x/p \rfloor + \lfloor x/q \rfloor - \lfloor x/\text{lcm}(p,q) \rfloor$. A range $a$ to $b$ is $f(b) - f(a - 1)$.

Primes. To test one number $n$, try divisors up to $\sqrt{n}$: $O(\sqrt{n})$. To find all primes up to $N$, use the sieve of Eratosthenes: cross out multiples of each prime, in about $O(N \log \log N)$. The same trial division up to $\sqrt{n}$ factorises $n$ and so counts its divisors.

Use math.isqrt(n) for whole-number square roots. int(n ** 0.5) goes through floating point and can be off by one for large $n$.

The number of ways to choose $k$ items from $n$ is $\binom{n}{k} = \frac{n!}{k!\,(n-k)!}$. Two standard ways to get it modulo a prime $p$:

• Pascal's rule $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$, as a DP table. Only additions, but $O(n^2)$, so for $n$ up to a few thousand.
• Factorial tables: precompute $i! \bmod p$ for $i$ up to $N$, then the inverse of $N!$ with pow(fact[N], p - 2, p), then work down with $\frac{1}{(i-1)!} = \frac{i}{i!}$. After $O(N)$ set-up each $\binom{n}{k}$ is three multiplications.

A key model: on a grid, a route from the top-left corner to a cell $a$ rows down and $b$ columns right, moving only down or right, is a choice of which $a$ of the $a + b$ moves go down, so there are $\binom{a+b}{a}$ routes. With blocked cells, combine this with a DP over the blocks and subtract the routes that pass through one (inclusion-exclusion).

Other tools: stars and bars ($\binom{n+k-1}{k-1}$ ways to share $n$ identical items among $k$ people), and the complement trick (count all, subtract the bad ones).