Skip to content

Latest commit

 

History

History
47 lines (41 loc) · 1.39 KB

README.md

File metadata and controls

47 lines (41 loc) · 1.39 KB

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