Programming
For GRCPC, SEERC and ICPC: the algorithms that come up again and again, with tested C++ code, and problems to write them yourself.
Basic techniques
- Prefix sums
The sum of any range in after one pass. And the reverse: many range additions with a difference array.
- Binary search on the answer
When "is it possible with ?" is monotone in , you find the smallest feasible in checks.
- Longest increasing subsequence
Its length in , keeping for every length the smallest possible last element.
Data structures
- Disjoint set union (DSU)
Merge sets and ask whether two elements are in the same one, in almost constant time per operation.
- Fenwick tree
Update one element and query a prefix sum, both in , with one array and two loops.
- Segment tree
Range queries for any associative operation, with point updates or, with lazy propagation, whole-range updates. per operation.
- Sparse table
Range minimum on a static array in , after preprocessing.
Graphs and trees
- BFS and 0-1 BFS
Shortest distances in an unweighted graph in . With weights only 0 and 1, the same with a double-ended queue.
- Dijkstra
Single-source shortest paths with non-negative weights, in .
- Topological sort
An order of the vertices of a DAG in which every edge points forward, in . Every DP on a DAG runs on top of it.
- Strongly connected components
Grouping the vertices of a directed graph into components where everyone reaches everyone, with two DFS passes, in . 2-SAT follows from it.
- Minimum spanning tree (Kruskal)
Sort the edges by weight and keep those that join two different components. , with a DSU.
- Lowest common ancestor (binary lifting)
The -th ancestor of every vertex in a table. With it, -th ancestor, LCA and tree distance, each in .
- Maximum flow (Dinic)
The maximum flow from to and, from the last BFS, a minimum cut. Bipartite matching and disjoint paths build on it.
Strings
- Prefix function (KMP)
For each position, the longest proper prefix that is also a suffix. It gives pattern search in and the "periods" of a word.
- Z-function
For each position , how many characters from agree with the start of the word. In , with a "window" we already know.
- String hashing
Compare any two substrings in after preprocessing. Probabilistic, modulo with a random base.
Mathematics
- Modular arithmetic and combinatorics
Fast exponentiation, inverses by Fermat's little theorem, and in after preprocessing.
- Linear sieve
The primes up to and the smallest prime factor of every number in . Then factorisation in .
How to work
Read the idea, close the page and write the algorithm from scratch. Submit on CSES. Look at the page's code only to compare, or when you need it ready-made and the rules allow printed material (e.g. the ICPC team reference document).
Submissions go to CSES or Codeforces themselves; no judge runs here.