Treap problems on CF only

Two Heads Are Better Than One — 100488L

8 years ago, # |

← Rev. 2 →

+20

Serega And Fun — 455D

T-Shirts — 702F

Database Query Engine — 100861D

→ Reply

dalex

8 years ago, # ^ |

+32

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.

→ Reply

8 years ago, # ^ |

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 2^nd query by a Treap. This is the solution I am talking about. Can anyone explain the above solution as well(2^nd query part)?

→ Reply

UnknownNooby

8 years ago, # |

+37

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 or std::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.

→ Reply

8 years ago, # ^ |

Thanks for the useful advice!

→ Reply

8 years ago, # ^ |

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?

→ Reply

8 years ago, # ^ |

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.

→ Reply

8 years ago, # ^ |

+10

Could you eleborate a bit? I mean what operations become linear?

→ Reply

8 years ago, # ^ |

+23

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.

→ Reply

8 years ago, # ^ |

+13

If you have problem for this reason wouldn't you have problems when input is sorted too?

→ Reply

8 years ago, # ^ |

+13

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.

→ Reply

8 years ago, # ^ |

+13

Yes, but if we allow equal elements both into left and right subtree, operations like count values less than x becomes linear.

→ Reply

8 years ago, # ^ |

+13

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

→ Reply

8 years ago, # ^ |

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.

→ Reply

8 years ago, # ^ |

← Rev. 2 →

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 with x + epsilon * i where i 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.

→ Reply

8 years ago, # ^ |

← Rev. 2 →

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.

→ Reply

8 years ago, # ^ |

No, I don't modify them. I say suppose I changed

→ Reply

8 years ago, # ^ |

← Rev. 3 →

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?

→ Reply

8 years ago, # ^ |

← Rev. 2 →

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

→ Reply

8 years ago, # ^ |

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

→ Reply

8 years ago, # ^ |

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

→ Reply

8 years ago, # ^ |

+23

Note, that adding 1 will only work with integers, but it's still easy to overcome

→ Reply

8 years ago, # ^ |

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?

→ Reply

8 years ago, # ^ |

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.

→ Reply

8 years ago, # ^ |

+13

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.

→ Reply

8 years ago, # ^ |

← Rev. 3 →

+10

UPD: removed, as I haven't read knightL comment well. (still you may find some implementation in previous revision)

→ Reply

8 years ago, # ^ |

ah right, now I noticed you said

unless we allow equal elements both into left and right subtree.

Well, yes we should allow it, don't see any reason to ban it in the first place

→ Reply

8 years ago, # ^ |

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.

→ Reply

8 years ago, # ^ |

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?

→ Reply

8 years ago, # ^ |

← Rev. 3 →

X will either be root (if has highest priority) or will go to left subtree of R

→ Reply

8 years ago, # ^ |

Cool, thanks!

→ Reply