By SecondThread, history, 6 months ago,

# 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!

• +969

 » 6 months ago, # |   +17 Your last tutorial was very good (Algorithms thread : Tree basic), now i cann't wait for this one anymore. thank you.
 » 6 months ago, # |   +5 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 :)
•  » » 6 months ago, # ^ |   0 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. :)))
•  » » 6 months ago, # ^ |   +66 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)
•  » » » 6 months ago, # ^ |   0 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.
•  » » » 6 months ago, # ^ |   +22 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.
 » 6 months ago, # |   +134 This is great! One possible improvement for your gym contests is sample explanations, consider creating those more often.
•  » » 6 months ago, # ^ |   -45 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.
•  » » » 6 months ago, # ^ |   +25 Xd
 » 6 months ago, # |   -81 Halloween is so pagan. Don't celebrate it.
 » 6 months ago, # |   +8 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.
 » 6 months ago, # |   0 Good
 » 6 months ago, # |   +28 The classic "Good Morning, Everyone" by SecondThread!!
•  » » 6 months ago, # ^ |   +11 *Everybody
 » 6 months ago, # |   +28 imagine not using splay trees #SplayGang
•  » » 6 months ago, # ^ |   +10 Splay will break in case you need persistence
•  » » » 6 months ago, # ^ |   +18 randomly splay a couple elements and call it a day
•  » » » » 6 months ago, # ^ | ← Rev. 2 →   +16 I think rpengsoo 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.
•  » » » » » 6 months ago, # ^ |   +11 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.
•  » » » » » 6 months ago, # ^ |   +16 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?
•  » » » » » » 5 months ago, # ^ |   +10 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.
•  » » » » » 6 months ago, # ^ |   +11 Sounds similar to scapegoat to me.
 » 6 months ago, # |   +25 been postponing even the thought of reading about treaps for god knows how many years xDNow I can finally have a proper intro, thanks for the help!
 » 6 months ago, # |   0 Though it's my first participation, I am really excited with the episodes. Happy Halloween !
 » 6 months ago, # |   0 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???
•  » » 6 months ago, # ^ |   +1 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.
•  » » » 6 months ago, # ^ |   0 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.
•  » » » » 6 months ago, # ^ |   +1 treap is heap on priorities + BST on keys. you use both properties
•  » » 6 months ago, # ^ |   +1 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?
 » 6 months ago, # |   0 Good!
 » 6 months ago, # |   +13 Why were half of the problems deleted D:
 » 6 months ago, # |   0 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)
•  » » 6 months ago, # ^ |   +5 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!
•  » » » 5 months ago, # ^ |   0 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!
 » 5 months ago, # | ← Rev. 2 →   +18 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
•  » » 5 months ago, # ^ |   +16 Well, I haven't coded it up yet, but I guess the solution is Guess at solutionSegment tree beats on the treap; i.e, maintain the 2nd maximum of each segment, and accordingly you can update sums.
•  » » » 5 months ago, # ^ |   0 I AC'd with this approach, but I wonder what the time complexity is. SpoilerIt 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++).
•  » » » 5 months ago, # ^ | ← Rev. 2 →   +10 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.
 » 5 months ago, # | ← Rev. 4 →   +43 There are a couple things that should be fixed in SecondThread's c++ treap template on his github: There is a missing parentheses in the "rangeAdd" function The value "data" isn't set in the constructor Vectors are used everywhere. This slows down the code a lot (because of the huge vector overhead). Just changing the vectors to std::array helped reduce the runtime of my D solution by a couple of seconds. Thanks!
•  » » 5 months ago, # ^ |   +34 Thanks for the suggestions! If you submit a PR, I'll definitely approve it :)
•  » » » 5 months ago, # ^ |   +15 I submitted the PR :) Let me know if there are any issues.
•  » » » » 5 months ago, # ^ |   +13 Awesome, thanks!
 » 5 months ago, # |   0 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
•  » » 5 months ago, # ^ |   +1 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.
•  » » 5 months ago, # ^ |   +1 I solved it using splaytrees. You can probably check my code out after the end of the contest.
 » 5 months ago, # | ← Rev. 3 →   0 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.
•  » » 5 months ago, # ^ |   0 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?
•  » » » 5 months ago, # ^ |   +1 No need for lazy propagation. Just store the hashing value for the original string and the reversed string. node updatingvoid m(const node& l, const node& r, node& res) { res.lhash=l.lhash+r.lhash*p[l.sz]; res.rhash=r.rhash+l.rhash*p[r.sz]; res.sz=l.sz+r.sz; } 
•  » » » » 5 months ago, # ^ |   0 It's true!I didn't thought that way, this is really cool.thank you very much for the explanation :)
 » 5 months ago, # |   +3 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.
•  » » 5 months ago, # ^ | ← Rev. 2 →   +10 Yeah I just saw there was a small mistake in C++ code. SecondThread forgot to set toProp to 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. left to right traversal:void show(Treap *me){ if(me == NULL)return; show(me->kids[0]); cout << (me->data) << ' '; show(me->kids[1]); } 
 » 5 months ago, # | ← Rev. 3 →   +3 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/1Is that right? or how can I solve this problem?last submission: 97961309
•  » » 5 months ago, # ^ |   +13 I've found my bug, I used value instead of rand-key when merging. Thanks!!!
 » 5 months ago, # |   +6 Auto comment: topic has been updated by SecondThread (previous revision, new revision, compare).
 » 7 weeks ago, # |   0 What is test case 19 on problem Z?