(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)
https://codeforces.net/problemset/problem/1949/B
Try to solve this in a time complexity that is not $$$O(n^2)$$$ or beyond. With this, you would reinvent:
Hall's theorem which I find very beautiful.
Pardon me if I failed to meet your constraints due to my inexperience.
Thanks for the suggestion!
Wouldn't a simple min(sort(aa) — sort(bb)) work? Ha-ha-ha. That would be too easy, and they'd certainly make n>=200 000 in such a case.
I'll think
Hehe, that's not it :). The solution is something way cooler !
Not codeforces, but I like this problem a lot. It is in romanian but translation should be relatively simple. Try to do it in $$$O(N)$$$.
Problem
but translation should be relatively simpleThen translate it, what's the problem?
The problem gives you a tree. A node is either a know-all that can answer queries or a know-nothing and has to ask one of its ancestors for the answer to the query. Each know-nothing might have a different ancestor they need to ask (for each node there is a $$$k$$$ that specifies that you should ask the $$$k$$$-th ancestor).
The task is to find for each node how many jumps a query makes (starting from that node) until it is answered.
The real issue is finding the k-th ancestor for each node in constant time.
Micro macro tree.
?
That's the solution to the 'The actual interesting part'.
I don't know what a micro macro tree is (although, I would not mind an explanation/resource).
Use a stack-like list.
Do a dfs from the root.
When entering a node add it to the end of the list. When exiting remove it from the list.
A node at depth $$$d$$$ with query of $$$k$$$ must look in the list at position $$$d-k$$$.
All the operations can be simulated on a
std::vectorfor example.The reason this is possible is that we solve the problem offline. If you were asked on the spot then this would not be doable (although maybe some persistent vector could work but at that point just use binary lifting)
https://cadmo.ethz.ch/education/lectures/HS18/SAADS/reports/5.pdf
Aliens' trick (the one that appeared in IOI16_aliens specifically). Do APIO10_commando first. Only person who managed to came up with that blind in-contest was LiTi ([user:jvcb] is only in-contest AC, but that was because he've known about the trick before)
Kruskal Reconstruction Tree/ Reachability Tree (online solution to that "How many nodes can be reached form node X using edges with weight <= W" common parallel binsearch problem). Very intuitive when you actually see it