CompProgCheatSheet

Cheat sheet for competitive programming

Done

• 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)

Needs testing

• fenwick tree
  • including 2d version
• prime sieve

Improvable

• 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

Todo

• 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

• 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.)