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

Merge two cartesian trees without rule keysA < keysB
Автор Jatana, история, 7 лет назад, По-русски

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?

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

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

Have you tried running it on random cases?

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

    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

    → Ответить
»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
»
7 лет назад, # |
← Rev. 7   Проголосовать: нравится +5 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    7 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

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

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

      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

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

    I have passed this task(T-Shirts) in 655 ms, submission — https://codeforces.me/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.

    → Ответить
»
7 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

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.

→ Ответить