rhezo's blog

By rhezo, history, 8 years ago, In English

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?

  • Vote: I like it
  • +30
  • Vote: I do not like it

| Write comment?
»
8 years ago, # |
Rev. 2   Vote: I like it +20 Vote: I do not like it
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +32 Vote: I do not like it

    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.

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

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

»
8 years ago, # |
  Vote: I like it +37 Vote: I do not like it

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.

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

    Thanks for the useful advice!

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

    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?

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

      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.

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

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

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

          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.

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

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

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

              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.

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

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

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

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

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

                  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.

                      10
                     /  \
                    9    10
                     \    \
                     10    20
                           /
                          10
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 years ago, # ^ |
                  Rev. 2   Vote: I like it 0 Vote: I do not like it

                  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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 years ago, # ^ |
                  Rev. 2   Vote: I like it 0 Vote: I do not like it

                  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.

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

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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 years ago, # ^ |
                  Rev. 3   Vote: I like it 0 Vote: I do not like it

                  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?

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 years ago, # ^ |
                  Rev. 2   Vote: I like it 0 Vote: I do not like it

                  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

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

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

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

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

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

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

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

                  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?

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

                  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.

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

                  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.

              • »
                »
                »
                »
                »
                »
                »
                »
                8 years ago, # ^ |
                Rev. 3   Vote: I like it +10 Vote: I do not like it

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

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

                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

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

                  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.

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

                  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?

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 years ago, # ^ |
                  Rev. 3   Vote: I like it +5 Vote: I do not like it

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

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

                  Cool, thanks!

        • »
          »
          »
          »
          »
          8 years ago, # ^ |
          Rev. 3   Vote: I like it 0 Vote: I do not like it

          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.

          1. Maintaining frequency for keys in every node.
          2. Make equal elements different, something I call coordinate expansion.

          Do you have any better ideas?

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

        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.

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.