Ayaz' Home Page

I managed to survive for quite a long time in Competitive Programming without knowing or understanding a lot of things. Granted, many of the things I mentioned below are very niche during the time I still actively participate in CP contests. I am not saying that you should not learn any of this. If you are interested in learning something, just go for it. (though knowing too much might be detrimental...)

Anyway, I am just making this for fun. Might be updated if I came across new things.

Note: this post is inspired by this.

• Generating Function
• How FFT and any of its variations e.g FWHT works
  • I only know they can be used to "multiply" polynomial
• Young tableaux
• Berlekamp-Massey algorithm
• Stirling numbers
• Simplex
• Mathematical formulation of Morbius Möbius inversion
  • I always think of Möbius inversion as a mathematical formulation of some inclusion-exclusion principle on GCD things
• Knuth-Morris-Pratt algorithm
  • Though I understand how Aho-Corasick trie works
• How to build LCP in Suffix Array deterministically in $O(n)$
  • I can imagine how to build it in randomized $O(n \log n)$ with hashing
  • I do know how to use it
• Suffix tree
• Suffix automaton
• Z-algorithm
• Manacher algorithm
• Eertree
• Delaunay triangulation
• Voronoi diagram
• Minkowski sum
• Any 3D geometry things
• Slope trick DP
• Connected components DP
• "Aliens" DP
• SOS DP
  • Kinda get the basic idea tho
  • (10-08-2023) understood, basically just a generalization of "GCD/LCM" things that I already used a lot (note: while I am not sure what the correct terminology is, I think instead of SOS DP what I didn't understand before is "Zeta transformation")
• Knuth optimization
  • I remember there is some quadrangle inequality, but that's it
• Li-Chao tree
• Segment tree beats
• Splay tree
• Link-cut tree
• Wavelet tree
• Top tree
• Matching in general graph (e.g Edmonds' blossom algorithm)
• Matroid intersection
• Directed MST (i.e minimum arborescence)
• Why Gomory-Hu tree is correct
• Kirchoff theorem the only Kirchoff I know is the one in physics
• Hungarian algorithm
  • I think at some point I understood it, but not anymore
• Fraction binary search, i.e do binary search but output the answer in fraction form instead of the decimal form (for example, 1/3 instead of 0.333).