I'm just in a mood to shitpost. Don't take it too seriously.
Things that I have heard of, but don't know (imagine how many things I haven't even heard of):
- Li-Chao Segment Tree
- Segment Tree Beats
- RMQ in O(n)/O(1)
- Any self-balancing tree except treap
- Link-cut tree
- Wavelet tree
- Mergesort tree
- Binomial heap
- Fibonacci heap
- Leftist heap
- Dominator tree
- 3-connected components in O(n)
- k-th shortest path
- Matching in general graph
- Weighted matching in general graph
- Preflow-push
- MCMF in O(poly(V,E))
- Minimum arborescence (directed MST) in O(ElogV)
- Suffix tree
- Online convex hull in 2D
- Convex hull in 3D
- Halfplane intersection
- Voronoi diagram / Delaunay triangulation
- Operation on formal power series (exp, log, sqrt, ...) (I know the general idea of Newton method)
- How to actually use generating functions to solve problems
- Lagrange Inversion formula
- That derivative magic by Elegia
- That new subset convolution derivative magic by Elegia
- How Elegia's mind works
- Sweepline Mo
- Matroid intersection
If you know at least 3 of these things and you are not red — you are doing it wrong. Stop learning useless algorithms, go and solve some problems, learn how to use binary search.
```
For 2023, I would append the list with:
- ChatGPT
- Github Copilot
- GPT-4
- Whatever the "generative AI" is
If you are a beginner, these so called "generative AI" are actually the same as those cryptic algorithms in competitive programming mentioned by Um_nik and you won't ever really use them once in your life, but learning the basics will definitely help you improve gradually.
```
I'm just in a mood to shitpost. Don't take it too seriously.
Things that I have heard of, but don't know (imagine how many things I haven't even heard of):
- Li-Chao Segment Tree
- Segment Tree Beats
- RMQ in O(n)/O(1)
- Any self-balancing tree except treap
- Link-cut tree
- Wavelet tree
- Mergesort tree
- Binomial heap
- Fibonacci heap
- Leftist heap
- Dominator tree
- 3-connected components in O(n)
- k-th shortest path
- Matching in general graph
- Weighted matching in general graph
- Preflow-push
- MCMF in O(poly(V,E))
- Minimum arborescence (directed MST) in O(ElogV)
- Suffix tree
- Online convex hull in 2D
- Convex hull in 3D
- Halfplane intersection
- Voronoi diagram / Delaunay triangulation
- Operation on formal power series (exp, log, sqrt, ...) (I know the general idea of Newton method)
- How to actually use generating functions to solve problems
- Lagrange Inversion formula
- That derivative magic by Elegia
- That new subset convolution derivative magic by Elegia
- How Elegia's mind works
- Sweepline Mo
- Matroid intersection
If you know at least 3 of these things and you are not red — you are doing it wrong. Stop learning useless algorithms, go and solve some problems, learn how to use binary search.
```
For 2023, I would append the list with:
- ChatGPT
- Github Copilot
- GPT-4
- Whatever the "generative AI" is
If you are a beginner, these so called "generative AI" are actually the same as those cryptic algorithms in competitive programming mentioned by Um_nik and you won't ever really use them once in your life, but learning the basics will definitely help you improve gradually.