Can anyone suggest me some Treap problems on CodeForces? I want to solve those problems that have solutions and editorials open.
I just can't implement a bug free Treap and most of the problems of Treaps I know are from SPOJ. Also I can't find Treap tag in problemset, I think these problems are under Data Structures tag, but how do I find them?
Serega And Fun — 455D
T-Shirts — 702F
Two Heads Are Better Than One — 100488L
Database Query Engine — 100861D
Hahaha, 100488L was intentionally made similar to a treap problem. In fact three deques are enough, but 95% of people use treap, and now it's one of the least solvable problem in that gym.
How to solve 455D by Treap? In the first 200 ranks and my friends standings, only one solution had done it with Treap. I can't understand how to answer the 2nd query by a Treap. This is the solution I am talking about. Can anyone explain the above solution as well(2nd query part)?
Unfortunately, there is no treap tag on codeforces, so it is really hard to find proper tasks fast, but I can recommend you implementing basic things with your treap.
Try implementing
std::map
orstd::set
with your treap.std::set
can be used in many tasks, so this way you can make sure that the core of your data structure is alright.This helped me a lot in past, for example I have solved 20C - Dijkstra? with splay tree, just to debug my own implementation.
Thanks for the useful advice!
Can you tell me one thing more, can a split-merge treap contain duplicate keys? If I want to insert a key already present, there is no way I can insert it right? To insert, I have to keep a frequency field in each node right?
You can modify the treap to contain duplicate keys but that will make some operations linear from logarithmic. It is better to have a frequency count in each node to handle duplicates.
Could you eleborate a bit? I mean what operations become linear?
Probably that depends on the way you treat the equal elements. If you say that all equal go to left / right subtree, than the tree with N nodes with equal keys will degenerate into a list. Thus all the operations will take O(N) time. Maybe there is some other way, but i'd prefer to simply make equal elements different in some way.
If you have problem for this reason wouldn't you have problems when input is sorted too?
No, it is absolutely different case. If I have a sorted input, I can still have a balanced tree with height O(log N). But only possible binary search tree for N equal elements seems to be a list, unless we allow equal elements both into left and right subtree.
Yes, but if we allow equal elements both into left and right subtree, operations like count values less than x becomes linear.
Count will still be possible to implement in
O(h)
time.Implement 2 operations: 1) Count number of elements less than x 2) Count number of elements less than or equal to x.
Both are just "split+get size of left(+merge back)"
Okay, so how exactly would you define split operation if both left and right subtrees can contain the same value? I understand that the tree will still be balanced because of random priority, but I'm not convinced how you will implement count in this structure.
I'm not really sure what problem is.
So I need to split tree to one that contains numbers =x.
Suppose for a second, that I replaced all numbers
x
withx + epsilon * i
wherei
is its number in order (so that its still a search tree) and epsilon is small. We can split this, right? But not a single comparison changed because I only care =x.Same with <= and > (you may need subtracting)
You may also check implementation (edited out of one of nearby comments) which will do first split correctly (didn't need second one) but it's easy with copy and paste.
You are however modifying the values in treap explicitly here. This is exactly what I claimed. You can modify the usual treap implementation like this or you can keep a frequency variable at every node. Without these modifications, all operations cannot be done in logarithmic time when there can be duplicates.
No, I don't modify them. I say suppose I changed
Okay, I think we are trying to imply the same thing. Suppose you changed, then I agree it is possible. But if you do not change, its not possible (unless you keep a frequency variable). Can we agree with each other now?
I don't think we imply the same thing.(more like opposite things)
Anyway, I think discussion is in dead end, so we'd probably should stop it
PS: implementation is available in nearby comment
Treap can easily answer a query "How many integers are there in range [a,b)?". You just hold count in every node like you would do for treap with implicit key. Then to get answer you split by a, then the rest by b and get count from the middle tree. Then merge everything back together. Getting frequency of x is same as asking number of integers in [x,x+1).
And split still works in the usual way. Let's assume we split node into trees with values < x and >=x . We arrive to some node. If it has value other than x, we do the usual. If it has value x, we know, that right subtree is definitely >=x since it has elements greater than or probably some equal to x. Thus root with its right subtree is the right tree for answer and we should split left subtree. Still works in O(height).
Note, that adding 1 will only work with integers, but it's still easy to overcome
knightL Just to confirm, so if we allow equal elements in both left and right subtrees, we can do the split as you defined above? Do you have an implementation of Treap written by you or anyone else?
Yes, we can. I prefer the implementation from e-maxx . There is also riadwaw's implementation in second revision of this comment with some fancy C++11 stuff :) . All the usual treap methods are in private section.
Jeez, it did not really seem to me that this can be done with treap, without any sort of modifications. It seems I have a different insert implementation which caused all the confusion. Sorry for the inconvenience, please ignore my other comments regarding this issue. And thanks for clearing it up.
UPD: removed, as I haven't read knightL comment well. (still you may find some implementation in previous revision)
ah right, now I noticed you said
Well, yes we should allow it, don't see any reason to ban it in the first place
Strange. I was sure, that there could be a problem with balancing since priorities don't actually define the tree structure. If all keys are different and all priorities are different, only one treap can be built. With same keys we may have any tree we like. Probably randomness still help in some way after all.
OK, I have one more stupid doubt. How do we allow equal elements into both left and right subtrees? While inserting a value X, we split it into 2 treaps L( < X) and R( > = X).
Now while merging X and R, we need to check priorities, and according to that an element will go into the left or right subtree of R right?
X will either be root (if has highest priority) or will go to left subtree of R
Cool, thanks!
As mentioned by knightL, the tree can degenerate into a list if there are all equal elements. I know two ways to get around this.
Do you have any better ideas?
Its work around should be simple. Keep counters for a value in nodes. I keep a counter to handle the multiple values issue. It shouldn't be a bother at all.
Can anyone suggest some good materials to start reading with? Most of the online materials related to treaps only mentioned how to add/delete nodes and the rotate method. It feels that there is a huge gap between practically applicable on programming problems from what was written on the paper.
http://codeforces.net/contest/420/problem/D