Cheat sheet for competitive programming
- binary search (tst)
- floyd-warshall (uva)
- bellman-ford (Kattis)
- dijkstra (Kattis)
- topological sort, kahn's algorithm (uva)
- minimum spanning tree, kruskals algorithm (kattis)
- segmenttree 2D (uva)
- matrix exponentiation (non-published impa uva, tst)
- trie (tst)
- matrix determinant (tst)
- fenwick tree
- including 2d version
- prime sieve
- gcd/lcm/eucl/diophantic
- hard to read; would inlining some code (and making a non-recursive version) help?
- A-star
- need to standardize format when including other algorithms
- Matrix exponentiation
- could save around 5 rows of code, and reduce line width by half
-
suffix array/tree (aho-corasick)
- suffix array is probably easier to write, and usually faster because of smaller memory footprint
-
closest pairs
-
convex hull
- jarvis walk or graham scan
- add note about 2x speedup by running top and bottom separately
- jarvis walk or graham scan
-
maxflow
- just assume DFS is already done
-
strongly connected components
- tarjan or path-based strong component algorithm
-
howto solve anything; step by step
-
geometry, maths and statistics
- useful formulas and when to use what
-
markov chain / MDP
-
Ordo-notation for all algorithms, and their limits etc.
- probably best if kept in a table, one per area (graph, string etc.)