Блог пользователя rhezo

Автор rhezo, история, 8 лет назад, По-английски

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?

  • Проголосовать: нравится
  • +30
  • Проголосовать: не нравится

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +20 Проголосовать: не нравится
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 лет назад, # |
  Проголосовать: нравится +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 - Алгоритм Дейкстры? with splay tree, just to debug my own implementation.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Thanks for the useful advice!

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      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 лет назад, # ^ |
          Проголосовать: нравится +10 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
            Проголосовать: нравится +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.

          • »
            »
            »
            »
            »
            »
            8 лет назад, # ^ |
              Проголосовать: нравится +13 Проголосовать: не нравится

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

            • »
              »
              »
              »
              »
              »
              »
              8 лет назад, # ^ |
                Проголосовать: нравится +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.

              • »
                »
                »
                »
                »
                »
                »
                »
                8 лет назад, # ^ |
                  Проголосовать: нравится +13 Проголосовать: не нравится

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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 лет назад, # ^ |
                    Проголосовать: нравится +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)"

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 лет назад, # ^ |
                    Проголосовать: нравится +5 Проголосовать: не нравится

                  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 лет назад, # ^ |
                  Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

                  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 лет назад, # ^ |
                  Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

                  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 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 лет назад, # ^ |
                  Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

                  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 лет назад, # ^ |
                  Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

                  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 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  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 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  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 лет назад, # ^ |
                    Проголосовать: нравится +23 Проголосовать: не нравится

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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 лет назад, # ^ |
                    Проголосовать: нравится +3 Проголосовать: не нравится

                  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 лет назад, # ^ |
                    Проголосовать: нравится +3 Проголосовать: не нравится

                  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 лет назад, # ^ |
                    Проголосовать: нравится +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.

              • »
                »
                »
                »
                »
                »
                »
                »
                8 лет назад, # ^ |
                Rev. 3   Проголосовать: нравится +10 Проголосовать: не нравится

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

              • »
                »
                »
                »
                »
                »
                »
                »
                8 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

                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 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  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 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  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 лет назад, # ^ |
                  Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  Cool, thanks!

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
          Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

          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 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.