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:

• [X] Fast MCMF (based on push/relabel) compatible with the flowgraph.
• [ ] O(n log n) Delaunay
• [ ] https://research.engineering.wustl.edu/~pless/506/l13.html
• [X] Shorter convex hull
• [X] Convex polygon preprocessing with closest point/tangent query in O(log n). Also Minkowski sums. (TODO: shorter)
• [ ] Dominator tree
• [X] Add `project selection' of Tardos/Kleinberg (7.11) to the flows section (non-trivial flow formulation)
• [ ] Link/Cut trees
• [X] Geometry: reuse geometry essentials, e.g. convex hull uses point and essentials uses P.
• [X] 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
• [X] 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.
• [X] 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
• [X] FFT -> Fast Walsh Hadamard transform / xor-convolution.
• [ ] Berlekamp Massey
• [X] Floor sum