(since I don’t have any following, this post will probably only get a few views, so in case you find it months/years later — yes, still relevant)
I am looking for some cool algorithms or data-structures, which are ingenious, clever and interesting, but also not prohibitively complicated, so it’s possible to re-discover them while solving some specific task.
My current knowledge for context
Re-invented before:
(stuff I came up with before I ever read or been taught about it)
- Polynomial string hashes
- Convex-Hull
- Persistent data structures like trees (by familiarity with functional programming, immutability and such)
- Graph min-span tree
Know-well:
- Various graph algorithms
- Various trees
- RMQ
- Prefix function, Aho-Corasick
- Dynamic programming
- DSU
- Parsing by recursion
Remember in general details:
- Suffix array
Coded previously, but never put effort to understand deeply and forgot:
- Graph min/max flow
- Suffix automaton
- Some limited RMQ-like structure, which can only do a subset of operations, but has a lower constant and lower memory usage (don’t remember the name)
This is not an exhaustive set of what I know, but hopefully it gives you a general idea to suggest stuff, which I likely don’t know and will find interesting.
Ideally looking for:
- CodeForces problem links
- a name of the algorithm/data-structure needed to solve it (which I’ll try not to use/Google before solving myself)
- Estimated difficulty to re-invent the algorithm and solve the corresponding problem(s)
