Jatana's blog

Merge two cartesian trees without rule keysA < keysB
By Jatana, history, 7 years ago, translation, In English

I invent method to merge two cartesian trees with maybe intersect keys. And want to know what is asymptotic of it.

method:

let's add to a standard cartesian tree field musorka

struct Node {
  Node *l = NULL, *r = NULL;
  int key, priority, cnt = 1;

  Node *musorka = NULL;
}

and when we want to merge trees A and B A->musorka = B

then write push

void push(Node *node) {
  if (!node->musorka) return;
  push(node->l);
  push(node->r);

  pair<Node*, Node*> spl = split(node->musorka, node->key);
  pair<Node*, Node*> spl2 = split(spl.second, node->key + 1);
  
  if (spl2.first) {
    node->cnt++;
  }

  node->l->musorka = spl.first;
  node->r->musorka = spl2.second;
  node->musorka = NULL;
}

then add this push to merge and split.

Maybe someone can estimate asimptotic of this or give counter test where it works n^2?

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

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

Have you tried running it on random cases?

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

    I was solved the problem:

    given array 1, 2, 3, .., n you need to move elements from [l, l + k) to [r, r + k)
    example:
    [1], [2, 3], [13], [8], [5], [6], [7] let l = 1, r = 5, k = 2 result should be [1], [], [], [8], [5], [3, 6, 2], [7, 13]

    I wrote this structure and it passed system test, but author's solution is different

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

After h (the height of the tree) merges to the same tree, all the nodes' musorka would be non-null.

In this case, each successive merge would have to traverse n nodes.

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    You can't merge same tree multiple times.

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

      What do you mean? My understanding is that if you have 3 trees, A, B, and C, you merge them by doing A->musorka = B; A->push(); A->musorka = C; A->push();

      (Typing on mobile is freaking hard ><)

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

        But then what's the problem?

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

          Eventually all the nodes (musorka) in A would be full.

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

            Why?

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

            I think A nodes would be full if we merge to A trees with size of A

            → Reply
»
7 years ago, # |
← Rev. 7   Vote: I like it +5 Vote: I do not like it

If I understood and implemented the idea correctly, I'm sorry to disappoint you, but the idea TLEs on 702F - Футболки. The problem basically can be solved with the thing you described (if it worked fast enough). Here is a link to my submission.

PS: This obviously is not a proof but at least might help in finding a counter sample.

PS2: It seems that the main reason why it TLEs is because a long path in the treap is created (the number of times "push" is called isn't large). This happens, because the above algorithm breaks the "heap" ordering by priority. Currently I'm trying to fix this, so I'll update this comment in about an hour.

PS3: I did a couple of optimizations but still couldn't fit the problem in 4 sec. Best I could achieve was AC with 20 sec on max test (I created a mashup with a different TL).

PS4: I managed to pass the problem with the same idea, but done in a different way. Here is the submission.

PS5: The same idea passes also for 911G - Запросы на массовое обновление. You can check a cleaner implementation here. The merge without the constraints is "merge_op".

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    Try rnd() % (a->sz + b->sz) < a->sz in merge, not a->prior < b->prior

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

      Well with this way of merging it still TLEd. But it did manage to get AC on the first 60 tests. I'll try some constant optimizations to see if I can make it fit.

      Submission

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

    I have passed this task(T-Shirts) in 655 ms, submission — https://codeforces.net/contest/702/submission/46662757.

    I do same things as mentioned in the blog, but without temporary musorka. I think a musorka is useless because we postpone a merge operation that we must do in the future and we don't get any time profit.

    → Reply
»
7 years ago, # |
  Vote: I like it +15 Vote: I do not like it

That looks like an amortization of naive merge: instead of splitting the second tree at the time of operation at all points at once, you postpone that until the data is really needed. I suspect that some simple potential method should be sufficient to proof the bound.

After some discussion with ifsmirnov it looks like amortized O(log2n) for each merge/split operation for me. Unfortunately, I don't have a rigid proof. The hand-waving goes like this: let's assume that we have an implicit segment tree instead of treap (the one which doesn't create a node unless there is a value in the corresponding subtree). That's somewhat worse than treap because it adds extra vertexes/levels, although structure may be different from treap. Afterwards, it looks like this post may help.

Another idea about constructing a bad test (I suspect that it will be O(n·log2n)): let's start with an array of 0... 2k - 1 sorted by reversed binary representations of numbers (e.g. 0, 4, 2, 6, 1, 5, 3, 7). Now let's merge adjacent elements and get {0, 4}, {2, 6}, {1, 5}, {3, 7}. Now let's merge adjacent elements as well and get {0, 2, 4, 6}, {1, 3, 5, 7}. And again, until we get a full tree. The idea is to always merge very "interleaved" trees.

→ Reply