Algorithms Thread Episode 9: Treaps
Good morning everyone!
Episode 9 of AlgorithmsThread comes out shortly after the Div2 round ends. This episode is on Treaps! It covers:
- Fundamentals of Treaps
- Splitting and Merging
- Range reversing
... and more! I also decided to keep up the super-high quality style and made a custom gym set with 5(+2) original problems to make sure you really understand everything that was covered in the lecture. The gym set will be released shortly after the lecture ends, and I hope that the problems will be challenging and fun, even for people who aren't seeing treaps for the first time.
If you have any questions or suggestions, feel free to leave them below. I hope you enjoy the problem statements, and, in the spirit of the upcoming holiday, I'll leave you all with this:
Update: The scoring distribution for this round will be: 1 — 1 — 1 — 1 — (+1) — (+1) — 1
Update2: Solution video is out now and solutions to all problems are available here. Hope you all enjoyed the contest!
Your last tutorial was very good (Algorithms thread : Tree basic), now i cann't wait for this one anymore. thank you.
I was sad at first because u didn't participated in today's contest as it was really an interesting one, but after watching this post, omg made my day :)
I wonder if SecondThread just missed today's div2 contest like I did since we are so used to the starting time of XX:35AM. :)))
I was up all night making sure there weren't bugs in the judge solutions actually. One of them was broken and I fixed it now (hopefully everything else is okay haha)
Damn, no wonder you can participate contest starting at 2:00AM our time. Really appreciate your efforts, hopefully you'll catch up some nice sleep soon.
Thanks a lot, David. That's a lot of effort you do for us, beginners and enthusiasts. Especially, when you also have a job, as well as make regular screen-cast of CF rounds participate side-by-side.
This is great! One possible improvement for your gym contests is sample explanations, consider creating those more often.
Has he asked for your advice ? He is at least doing CP related things instead people like you who just make useless blogs , comments , doing Leetcode/interview problems for getting more contribution and low rated subscribers . He deserves to be on top of contribution list not you.
Unrelated, but I was kind of scared when you brought an axe infront of that nice little tree in your beautiful episode...In any case, learned a lot of new concepts from your fabulous video. Waiting for the custom gym.
The classic "Good Morning, Everyone" by SecondThread!!
imagine not using splay trees #SplayGang
Splay will break in case you need persistence
randomly splay a couple elements and call it a day
I think rpeng and Friends actually came up with a legit way of handling this. It has something to do with splaying if you ever reach 4*log(n) height I think, but he would be able to explain it much better than I could.
Of course, you can just use treaps too, which is probably way easier in this case.
i wonder what would happen if you kept track of the longest path in the tree, and then splayed the deepest node a bunch of times before you start keeping track of the roots for persistence.
Paging Darooha, I think his theory was to take all the nodes that are too deep, and splay a few extra per iter or something.
I think the constant factor overhead of this is massive though.
The bigger issue is I don't know problems that force persistent BSTs: usually some kind of 2~3 layer bucketing works just as well for them (and are probably just as silly to code). Are there such problems with tight resource constraints?
Sorry for the necropost. I think Поиск идеи by izban is a great task to benchmark persistent BST. For that task, I heard persistent treap fails because of tight ML (which is 1GB lol). Intended solution uses persistent 2-3 trees.
As for the thread in general, I also only know how to use splay trees, but the issue with persistency made me to seriously consider learning other BBSTs. I'm also bad at implementing splay trees, so I wonder if learning treaps will make my life easier.
Sounds similar to scapegoat to me.
been postponing even the thought of reading about treaps for god knows how many years xD
Now I can finally have a proper intro, thanks for the help!
Though it's my first participation, I am really excited with the episodes. Happy Halloween !
SecondThread, Afaik I remember, you said that when you create Treap on N numbers, you create N Nodes and then merge them. But when merge is done, it is assumed that all elements on the left treap is smaller than the numbers on the right Treap and merging is done only on the basis of priority. But if I were to make a Treap on unsorted array, then the inorder traversal of the array wont give a sorted representation of the array. Is there an inconsistency or have I miss understood something???
you assume the keys on the left are smaller than the keys on the right when doing a merge. in the case of an array, the keys are the indices, not the values in the array.
Still my point sustains, (in his implementation) we are not creating the treap based on the key but using the priorities (at least while merging). My understanding says, the inorder of treap should give sorted array, and the priorities helps in maintaining the height of treap of order O(logn). I dont see the key being used to create the treap.
treap is heap on priorities + BST on keys. you use both properties
It is okay that the inorder traversal of the treap isn't actually a sorted array. When you do merges, you keep the stuff that is on the left on the left, and the stuff on the right on the right, so you can force the left-right order to be whatever you want. The top-bottom order is randomized to keep it log-n tall. Does that make sense?
Why were half of the problems deleted D:
Is it possible to do "treap-beats?" More specifically, is it possible to do the segtree-beats operations, such as range-mod updates and range-sum queries, on a treap? (while still allowing for standard split/merge ops on a treap)
It sure is! Remember when I said that "Anything you can do with segment trees you can also do with Treaps"? That includes all the cool segment tree tricks like persistance and STBeats!
Two more questions about segtrees vs treaps :)
In some segtree problems, you want to store a data structure, such as a CHT, over all of the nodes in that range. For example, an approach to this problem would be to store a segment tree of CHT's. Because each node in the segment tree could have up to O(n) children, would it also be possible to do this with a treap, as in a treap you might need to recalc a node many times?
Also, are there 2-d treaps? Sorry if it's not a great question, but I can't really think of a good way to implement it.
Thanks for the help!
Could someone provide a hint for the "Grim Treaper" problem? Doing all types of queries is simple but maintaining the sum is actually tricky :D
Well, I haven't coded it up yet, but I guess the solution is
Segment tree beats on the treap; i.e, maintain the 2nd maximum of each segment, and accordingly you can update sums.
I AC'd with this approach, but I wonder what the time complexity is.
It probably has the log^2 factor that normal segtree beats has (with range set min and range add queries), but the treap split/merge ops might mess that up. Mine ran in about 2 seconds (using c++).
Thanks a lot for the solution. I haven't know "the segment beats" technique before (should have checked all the AlgoThread videos). If someone else is interested what it is, check the video or this amazing blog post.
Can someone share test case 3 of this problem? I'm getting WA :(
There are a couple things that should be fixed in SecondThread's c++ treap template on his github:
Thanks for the suggestions! If you submit a PR, I'll definitely approve it :)
I submitted the PR :) Let me know if there are any issues.
I would like to know if the last problem (problem Z: trick or treap) could be solved using splay tree..., anyone could solve this problem using splay tree?. If its possible, I would really like to discuss about it after the contest end
I briefly mentioned this in the video, but really the only purpose of a treap is to keep your trees shallow. Treaps do it nondeterministicly which makes it easy to code, but there are other things you can do like a splay tree or red black tree that work too. So basically yes, pretty much everything* that is possible with a treap is also possible with a splay tree if you want.
*things that use persistent treaps might have a faster runtime than persistent splay trees in theory, but there are likely workarounds in that one case. The reason this is different is that splay trees are amortized to log, but that amortization isn't taken into account if you make it persistent.
I solved it using splaytrees. You can probably check my code out after the end of the contest.
Can anyone give some hints on B and Z? Thanks in advance!
UPD: solved B using string hashing.
UPD2: solved Z by maintaining parent nodes.
I tried to implement this on B but I couldn't.
How did you store and update the indexes on each node in the treap? did you use lazy propagation?
No need for lazy propagation. Just store the hashing value for the original string and the reversed string.
I didn't thought that way, this is really cool.
thank you very much for the explanation :)
Did someone manage implement the C++ code from the GitHub, for some reason I get wrong answer on test case 8 on the first problem, and cannot see the test case in order to debug.
Yeah I just saw there was a small mistake in C++ code. SecondThread forgot to set
toPropto 0 which causes kind of undefined behaviour.
You can even remove it because it's not needed. Also removed from your code some unneeded things like
sum, toProp, used
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());only once and time improved from 4400ms to 2500ms. You could also, instead of splitting the tree to get the value at some position, use that fact, that traversal of the tree from left to right is the left to right traversal of the array.
In Problem C, I got 15 TLE on test 15. My solution is treap with lazy-tags.
- Tags 1: flip each node on the subtree
- Tags 2: reverse the subtree
- Tags 3 = Tags 1 + Tags 2
- Tags 4/5: set each node = 0/1
Is that right? or how can I solve this problem?
last submission: 97961309
I've found my bug, I used value instead of rand-key when merging. Thanks!!!
Auto comment: topic has been updated by SecondThread (previous revision, new revision, compare).
What is test case 19 on problem Z?
SecondThread Does it matter to split with the condition
key < node.valueor
key <= node.value?
I'm solving CF Education Round 15 F, If I use
key < node.value, I am getting AC, If I use
key <= node.value, I am getting TLE.
Any idea why would that happen?
Also does different ways
insertfunction affect the running time a lot? I'm getting AC if I use
But TLE if I use
I'm not understanding why? Can you please help me?
Similar issue (?)
Thank you TheScrasse.