Former UPC2 SWERC notebook

Main branch under update, checkout 2017 branch for the version used in contest

Stubs should hold mains to problems to check algorithm correctness

Things to Add

Check KTH pdf again for new additions, and changes in compilation

• Centroid Decomposition
• Better Structured MaxFlowMinCost?
• Berlekamp-Massey
• Linear Recurrentce

Things to Delete

• Rolling Binomial
• Binomial Mod Prime

Things UPC PDF has

• gomory_hu (maxflow tree)
• edge coloring
• LCS between all substrings
• negative edges maxflow mincost
• Changes to maxflow mincap etc
• Fast Walsh-Hadamart transform

Status

• combinatorial
• data-structures
  • FenwickTree
  • FenwidckTree2d
  • LineContainer
  • RMQ
  • OrderedSet
  • HashMap
  • Segment Tree (temporaly removed)
  • Treap (need to understand)
  • UnionFind (temporaly removed)
• geometry
• graph
  • 2sat
  • ArticulationPointAndBridges
  • Biconnected components
  • Binary Jumps
  • Eularian Cycle
  • Fast MaxFlow
  • LengauerTarjan/Dominator Tree
  • LinkCutTree (need to understand)
  • MaxWeightBipartiteMatching
  • MaxflowMinCap
  • MaxflowMinCost (refactor?)
  • MinCostBipartite (removed)
  • MinimalArborescenses (need to understand)
  • SCC (Fix to struct)
  • Stable Marriage
  • Global Mincut
• math
• number theory
• numerical
  • Determinant
  • FTT
  • NTT
  • Integrate
  • MatrixInverse
  • PolyInterpolate
  • PolyRoots
  • Simplex
  • SolveLinear
  • SolveLinear2
  • SolveLinearBinary (add base finding)
• strings
  • Ahocorasick
  • CYK
  • Hashing
  • KMP
  • Manacher
  • MinRotation (understand)
  • Palindromic Tree (understand)
  • Suffix Array
  • Suffix Automaton (understand)
  • Suffix Tree (understand)
  • Z
• various
  • Understand DP optimizations
  • Delete Java?

Credits to students of KTH Royal institute and Simon Lindholm for the base template of the Latex and many original source codes, and to all contributors to the original UPC2 Notebook (Michael Sammler and Eric Valls)