hielitos's blog

Help with Treap
By hielitos, history, 5 years ago, In English

Hi, my question is related with Treaps, and maybe random numbers.

I was trying to solve this problem: C2. Exam in BerSU (hard version), but during the contest I made this solution with Treap: My code and i got TLE.

Then I read the problem again and I solved it based on the limit for the time t_i

And after the contest I asked if somebody had solve this problem with treap and the answer was yes and this is the code Solution with treap

Now, I am asking to myself if my code doesn't work because of the way I use the random number generator (maybe the treap is unbalanced or i don't know) or my implementation of the treap is wrong.

I have no idea why my solution doesn't work

Any help will be appreciate. Thanks in advance and please feel free to asked about any part of my code. Here is the discussion after the contest: Here , The blog about the random generator I use and The referenced I used to code my treap

  • Vote: I like it
  • -3
  • Vote: I do not like it

Comments Comments (11)
| Write comment?
»
5 years ago, # |
  Vote: I like it -28 Vote: I do not like it

feel free to asked about any part of my code

Feel free to explain every part of your code

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Hey hi, I am trying to learn treaps could u please suggest how could we use segment tree , priority queue ,multiset or treap any of these for solving these question,how could it be useful. Also I want to know that using treap could we implement dynamic prefix array sum.

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

    Hi, my approach was as follow:

    I solved from left to right ( i.e. I solved first for 1, next for 2 and so on.. ). Lets supposed we are in the i-th position, then we have two options:

    1) If the sum of the range [ 1 , i ] is less than or equal to M, then we don't have to erase any element.

    2) If the sum of the range [ 1 , i ] is greather than M, then we have to find the largest number of elements such that their sum plus A_i is less than or equal to M, right? For this you can sort the elements in the range [ 1 , i-1 ] and fin the largest prefix whose sum plus A_i is less than or equal to M and this will be the answer. But you can't sort everytime because of the time limit, that's why I used Treap, I kept the sums of every subtree and find the greathest number of elements could be do in O( lg N )

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Try inlineing maybe? so like inline ll getSum() should make it faster. Basically it reduces function call overhead. since you will be calling such methods a lot, inline the frequently called methods

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

I just spent quite a while trying to figure out why your code is so slow, but as far as I can tell there's no significant difference between your solution and mine. I'll look into it more tomorrow. Edit: meooow found the problem, see the comment below.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Also thanks to you, as you can see in the comment below, the error was found, but i found your code and your comments very helpful :D

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      No problem. I feel very lucky that I didn't have this problem since my treap code was based on the same cp-algorithms.com article that you used. I had made your code as close to mine as possible without changing how it functions, and I was going to start to replace your functions with mine one-by-one to figure out where the problem is. This had me going like WTF????? for hours :)

      → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +20 Vote: I do not like it

I have located the problem, took quite a while.
It is caused by a combination of your split and insertNode implementations and the fact that the treap needs to act as a multiset.

Consider that you want to fill the treap with multiple copies of a single value. In insertNode, when t->priority >= nd->priority and t->value equals nd->value, insertNode is called on the right child. This means that as long as the new node has lower priority than the current node, you keep moving down through right children.

When the priority is found greater than current node, you split the current node. In split when t->value equals value, you move to the left child. This means that the treap is split into < value and >= value. For a treap with the same value in every node, the entire treap goes to the right portion. Now you attach this treap to the right child of new node.

Perform $$$n$$$ such insertions, and viola! You have successfully obtained the worst possible binary search tree configuration, a degenerate tree of height $$$n$$$.

How to avoid this? Either change your split to split into <= value and > value, or change your insertNode to go into the left child when values match. Don't do both however, because that would reintroduce the problem. Alternately, consider a (split, merge, merge) based insert implementation which will not be affected by this.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Yes! You were right, it worked. Thank you so much, I spent a lot of time trying to find the reason, now thanks to you I will be able to solve problems that involved Treaps.

    I'm so happy :DD

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Glad to help :)
      It is interesting that such a specific scenario can remove the randomness on which the treap relies.

      → Reply