contests

SRT Technique Binary search on the answer If checking an answer is easier than finding it, and the check is monotone, search for the answer by halving. O(log D · cost of a check) 2 problems DS Data structure Fenwick tree Prefix sums with updates in O(log n) in a single array: blocks as long as the lowest one bit of the index. O(log n) per prefix sum and per update 2 problems GRA Algorithm Breadth-first search Walks a graph in layers and finds paths with the fewest edges in O(V + E). O(V + E) 2 problems GRA Algorithm Bridges and articulation points Streets and crossroads without which a graph falls apart: one depth-first search with the numbers tin and low, O(V + E). O(V + E) 2 problems GRA Algorithm Floyd–Warshall algorithm Shortest paths between all pairs of vertices in O(n³): dynamic programming over allowed transfers. O(n³) 2 problems GRA Algorithm Dinic's algorithm Maximum flow in phases: a layered network, a blocking flow, pointers; O(V²E), and O(E√V) in unit networks. O(V² E) 2 problems GRA Algorithm Bipartite matching The largest number of pairs in a bipartite graph: Kuhn, Hopcroft–Karp, the theorems of König and Hall. O(E √V) 2 problems GRA Algorithm Eulerian path Go along every edge exactly once: the odd-vertex rule and Hierholzer's algorithm in O(E). O(V + E) 3 problems GRA Algorithm Heavy paths Path queries on trees: heavy paths cut any path into O(log n) array stretches under a segment tree. O(log² n) per query 1 problem GRA Algorithm Centroid decomposition Splitting a tree by centroids: log₂ n levels, and the nearest marked vertex in O(log n) after every mark. O(log n) per mark and per question 1 problem STR Algorithm The Aho–Corasick algorithm Every occurrence of thousands of words in one pass: a trie of the words plus failure links, as in the prefix function. O(n + Σ|wᵢ| + z) 1 problem DP Technique Dynamic programming Reduce a problem to subproblems, solve each once and keep the answers in a table. states × transitions 2 problems DP Technique Interval DP The state is an interval [i, j], the transition is where to cut it: search trees, matrix chain order, sawing. O(n³) 2 problems DP Technique Bitmask DP The state is a subset written in the bits of a number: an exact travelling salesman, assignments, tilings by profile. O(2ⁿ · n²) for the travelling salesman 2 problems DP Technique Digit DP Lucky tickets in any range in one pass over the digits: 55,252 out of a million, and any range up to 10¹⁸, in about a millisecond. O(D · 10 · S) 2 problems DP Technique Convex hull trick A minimum of lines instead of a search: 1776 catalogue tests split into sandbox runs, and a quadratic DP becomes linear. O(n) 2 problems DP Technique Knuth and divide-and-conquer optimisations 45 thousand towns on a map by population class: 3.5 million evaluations instead of five billion, because the best split is monotone. O(k · n log n) 2 problems PAR Technique Greedy algorithms The best step now with no looking back: when it is optimal, when almost, and how to prove it. usually O(n log n): a sort or a heap 2 problems PAR Technique Backtracking Build a solution step by step, check at once and retreat from dead ends: sudoku, queens, colourings. O(bᵈ) in the worst case 2 problems PAR Technique Divide and conquer Cut, solve the parts the same way, glue; what it costs follows from the levels of the recursion tree and the master theorem. T(n) = a·T(n/b) + f(n) 2 problems NUM Algorithm Big integers Numbers longer than a machine word: digits in base 10⁹ or 2³⁰, carries, column methods and expensive printing. addition O(n), column multiplication and division O(n²), printing in decimal O(n²) or O(M(n) log n) 2 problems NUM Algorithm Fast Fourier transform The discrete Fourier transform in O(N log N): spectra, convolutions, multiplying polynomials and big numbers. O(N log N) 2 problems GEO Technique Vectors and orientation The sign of the cross product is a left or right turn; almost all of computational geometry stands on it. O(1) per turn 2 problems GEO Algorithm Convex hull The smallest convex polygon containing all the points, in O(n log n). O(n log n) 2 problems TEC Technique Big O How work grows with the data: O, Ω and Θ, rules for estimating code, and where asymptotics mislead. estimated from the program text 1 problem TEC Technique Fast input and output A million numbers in tens of milliseconds instead of a second: reading it all at once, a buffer and one write of the output. O(size of the input) 1 problem TEC Technique Coordinate compression Replace values up to a billion by their ranks in order, and build arrays and trees over the ranks. O(n log n) to compress 2 problems TEC Technique Bit tricks A number as a set of flags: masks, the lowest set bit, counting ones and going through subsets without recursion. O(1) per operation on a word 1 problem