Блог пользователя SecondThread

Автор SecondThread, история, 4 года назад, По-английски

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
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +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 :)

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 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. :)))

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +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)

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 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.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +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.

»
4 года назад, # |
  Проголосовать: нравится +134 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится -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.

»
4 года назад, # |
  Проголосовать: нравится +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.

»
4 года назад, # |
  Проголосовать: нравится +28 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +28 Проголосовать: не нравится

imagine not using splay trees #SplayGang

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    Splay will break in case you need persistence

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +18 Проголосовать: не нравится

      randomly splay a couple elements and call it a day

      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 2   Проголосовать: нравится +16 Проголосовать: не нравится

        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.

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится +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.

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится +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?

          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
              Проголосовать: нравится +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.

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится +11 Проголосовать: не нравится

          Sounds similar to scapegoat to me.

»
4 года назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

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!

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 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???

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +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.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +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?

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Good!

»
4 года назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Why were half of the problems deleted D:

»
4 года назад, # |
  Проголосовать: нравится 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)

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +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!

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 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!

»
4 года назад, # |
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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится

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

    Guess at solution
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      Spoiler
    • »
      »
      »
      4 года назад, # ^ |
      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.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Can someone share test case 3 of this problem? I'm getting WA :(

»
4 года назад, # |
Rev. 4   Проголосовать: нравится +43 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится 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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

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

»
4 года назад, # |
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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 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?

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

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

      node updating
      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        It's true!

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

        thank you very much for the explanation :)

»
4 года назад, # |
  Проголосовать: нравится +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.

  • »
    »
    4 года назад, # ^ |
    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:
»
4 года назад, # |
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/1
Is that right? or how can I solve this problem?
last submission: 97961309

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What is test case 19 on problem Z?

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

SecondThread Does it matter to split with the condition key < node.value or 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 insert function affect the running time a lot? I'm getting AC if I use

void insert(pitem &t, pitem it){
    pitem l, r;
    split(t, l, r, it->value);
    merge(t, l, it);
    merge(t, t, r);
}

But TLE if I use

void insert(pitem &t, pitem it){
    push(t);
    if(!t) t = it;
    else if(it->prior > t->prior) split(t, it->l, it->r, it->value), t=it;
    else insert(t->value <= it->value ? t->r : t->l, it);
}

I'm not understanding why? Can you please help me?