SecondThread's blog

By SecondThread, history, 6 weeks ago, In English

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!

 
 
 
 
  • Vote: I like it
  • +969
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it +17 Vote: I do not like it

Your last tutorial was very good (Algorithms thread : Tree basic), now i cann't wait for this one anymore. thank you.

»
5 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

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 :)

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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. :)))

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +66 Vote: I do not like it

    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)

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +22 Vote: I do not like it

      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.

»
5 weeks ago, # |
  Vote: I like it +134 Vote: I do not like it

This is great! One possible improvement for your gym contests is sample explanations, consider creating those more often.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it -45 Vote: I do not like it

    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.

»
5 weeks ago, # |
  Vote: I like it -81 Vote: I do not like it

Halloween is so pagan. Don't celebrate it.

»
5 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

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.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Good

»
5 weeks ago, # |
  Vote: I like it +28 Vote: I do not like it

The classic "Good Morning, Everyone" by SecondThread!!

»
5 weeks ago, # |
  Vote: I like it +28 Vote: I do not like it

imagine not using splay trees #SplayGang

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Splay will break in case you need persistence

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

      randomly splay a couple elements and call it a day

      • »
        »
        »
        »
        5 weeks ago, # ^ |
        Rev. 2   Vote: I like it +16 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it +11 Vote: I do not like it

          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.

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it +16 Vote: I do not like it

          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?

          • »
            »
            »
            »
            »
            »
            4 weeks ago, # ^ |
              Vote: I like it +10 Vote: I do not like it

            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.

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it +11 Vote: I do not like it

          Sounds similar to scapegoat to me.

»
5 weeks ago, # |
  Vote: I like it +25 Vote: I do not like it

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!

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Though it's my first participation, I am really excited with the episodes. Happy Halloween !

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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???

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        treap is heap on priorities + BST on keys. you use both properties

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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?

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Good!

»
5 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

Why were half of the problems deleted D:

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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)

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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!

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 weeks ago, # |
Rev. 2   Vote: I like it +18 Vote: I do not like it

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 weeks ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    Well, I haven't coded it up yet, but I guess the solution is

    Guess at solution
    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I AC'd with this approach, but I wonder what the time complexity is.

      Spoiler
    • »
      »
      »
      4 weeks ago, # ^ |
      Rev. 2   Vote: I like it +10 Vote: I do not like it

      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 weeks ago, # |
Rev. 4   Vote: I like it +43 Vote: I do not like it

There are a couple things that should be fixed in SecondThread's c++ treap template on his github:

  1. There is a missing parentheses in the "rangeAdd" function
  2. The value "data" isn't set in the constructor
  3. 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!

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I solved it using splaytrees. You can probably check my code out after the end of the contest.

»
4 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      No need for lazy propagation. Just store the hashing value for the original string and the reversed string.

      node updating
      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It's true!

        I didn't thought that way, this is really cool.

        thank you very much for the explanation :)

»
3 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it +10 Vote: I do not like it

    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:
»
3 weeks ago, # |
Rev. 3   Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    I've found my bug, I used value instead of rand-key when merging. Thanks!!!

»
3 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

Auto comment: topic has been updated by SecondThread (previous revision, new revision, compare).