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
feel free to asked about any part of my code
Feel free to explain every part of your code
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.
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 )
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 methodsThanks, but it didn't work :c 55904902
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.
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
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 :)
I have located the problem, took quite a while.
It is caused by a combination of your
splitandinsertNodeimplementations 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, whent->priority >= nd->priorityandt->valueequalsnd->value,insertNodeis 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
splitwhent->valueequalsvalue, you move to the left child. This means that the treap is split into <valueand >=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
splitto split into <= value and > value, or change yourinsertNodeto 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.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
Glad to help :)
It is interesting that such a specific scenario can remove the randomness on which the treap relies.