Part 10
Problem solving
The techniques competitive programming is built on, taught against the constraint that decides which one you need — and drilled on a judge.
-
10.1
How to read a problem and its limits
The constraints are half the statement, and they usually name the algorithm.
-
10.2
Counting the work you actually do
Deriving the complexity of the code in front of you, including the parts that do not look like loops.
-
10.3
The contest template and fast I/O
The four lines every solution starts with, what they are worth, and the input shapes you will meet.
-
10.4
Sorting, comparators, and coordinate compression
Ordering by whatever you like, without breaking the rule that makes sorting work.
-
10.5
Binary search: on a range, and on the answer
Halving a sorted range, and the larger trick of halving the space of possible answers.
-
10.6
Two pointers and sliding windows
Two indices that only move forward, and why that makes a nested loop linear.
-
10.7
Prefix sums and difference arrays
Pay once up front so every range question afterwards costs two lookups — and the same trick run backwards, so every range update costs two writes.
-
10.8
Monotonic stacks
A stack you keep sorted as you go, and the amortised argument that makes "for each element, look left until…" a single linear pass.
-
10.9
Deques and sliding-window extrema
A monotonic stack with an expiry date: the maximum of every window, in one pass and no logarithms.
-
10.10
Hashing, frequency maps, and multisets
Four ways to count things, the one that is fifty times faster, and the hash-map attack that turns a linear solution into a quadratic one.
-
10.11
Recursion and backtracking
Choose, explore, un-choose — and the two things that turn an exponential search into a feasible one.
-
10.12
Bitmasks: enumerating subsets and permutations
A subset is an integer. What that buys you, what it costs, and the three idioms worth memorising.
-
10.13
Greedy, and proving it with an exchange argument
Three plausible greedy rules for the same problem, two of them wrong, and the argument that tells you which is which before the judge does.
-
10.14
Divide and conquer
Split, solve, combine — and the three questions that decide whether the combine step is worth what the split costs.
-
10.15
Meet in the middle
Split the input in half, enumerate both halves, and let the two lists find each other — 2^n becomes 2^(n/2), and n = 40 becomes possible.
-
10.16
Representing graphs
Three ways to store a graph, the one that is nine times faster to build, and the graphs you never store at all.
-
10.17
BFS, 0–1 BFS, and multi-source BFS
One queue, shortest paths in edges — and the two variations that cover most of what a contest asks for.
-
10.18
DFS: components, cycles, bridges
The same loop as BFS with a stack instead of a queue — and the three things that only a depth-first order can tell you.
-
10.19
Topological order and DAG DP
Put a directed acyclic graph in an order where every edge points forward, and dynamic programming over it becomes a single sweep.
-
10.20
Union-Find
Two arrays, twenty lines, and a structure that answers "are these connected" fast enough that the answer stops being the interesting part.
-
10.21
Dijkstra
A heap, a distance array, and one line of lazy deletion — plus the reason it needs non-negative weights, demonstrated rather than asserted.
-
10.22
Bellman–Ford and Floyd–Warshall
What to do when Dijkstra's precondition fails, and the two algorithms that do not need it.
-
10.23
Minimum spanning trees
Connect everything for the least total weight. Two greedy algorithms that always agree, a property that is not shortest paths, and one that is more useful than it looks.
-
10.24
Tree DP and rerooting
A tree is a DAG once you root it, so one sweep answers a question about every subtree. Two sweeps answer it for every possible root at once.