Team Code Reference

A Team Code Reference for competitive programming contests. The original version that went to ICPC WF 2016 may be found here. A more recent version for the 2018/2019 season is here.

Open:

• Fast MCMF (based on push/relabel) compatible with the flowgraph.
• O(n log n) Delaunay
• https://research.engineering.wustl.edu/~pless/506/l13.html
• Shorter convex hull
• Convex polygon preprocessing with closest point/tangent query in O(log n). Also Minkowski sums. (TODO: shorter)
• Dominator tree
• Add `project selection' of Tardos/Kleinberg (7.11) to the flows section (non-trivial flow formulation)
• Link/Cut trees
• Geometry: reuse geometry essentials, e.g. convex hull uses point and essentials uses P.
• Facts about the Tutte matrix and Edmonds algorithm. Also https://www.mimuw.edu.pl/~mucha/pub/mucha_sankowski_focs04.pdf
• https://github.com/koosaga/DeobureoMinkyuParty/blob/master/teamnote.pdf
• Add: Max divisors under some powers of 10.
• More about the Tutte matrix, and some applications like the Chinese postman problem.
• Unify Treap and Sequence.
• Brief write-up on continued fractions. Also Farey sequence / Stern Brocot Tree.
• Test CHT on https://codeforces.com/contest/1083/problem/E
• Useful probability stuff, martingales, gamblers ruin etc
• Totient summatory function and other mobius stuff
• FFT -> Fast Walsh Hadamard transform / xor-convolution.
• Berlekamp Massey
• Floor sum