stostap's blog

By stostap, history, 7 years ago, In English

Hi community,

I'm big fan of treaps, but this task makes me feel stupid. https://www.e-olymp.com/en/problems/2957

There is no English translate for some reason. Task: Given N single-element lists with integers 1..10^9, perform next queries:

  • merge L R -> take two already exist lists and create a new one, equal concat(L,R)
  • head L -> create two new lists: first contains first element of L, second — the rest of L.
  • tail L -> create two new lists: first contains all L without last element, second — last element.

For every new list you need to output sum of it's elements.

I've did it with persistent treap — for every merge query: merge(root[L], root[R], root[++versions]), for head — split(root[L], root[nextV()], root[nextV()], 1) for tail — split(root[L], root[nextV()], root[nextV()], cnt[root[L]]-1);

But this fails with "Memory Limit" as for every query it creates at least Log new nodes

typedef long long LL;
#define N 13000005
#define MOD 1000000007
int root[300005] , c;
struct Treap
{
    int sum[N];
    int nodecnt;
    int L[N] , R[N] , cnt[N];
    int key[N];
    void clear() {
        nodecnt = 0;
    }
    Treap () {clear();}
    bool hey(int A , int B) {
        return (LL)rand() * (cnt[A] + cnt[B]) < (LL)cnt[A] * RAND_MAX;
    }
    int newnode(int x) {
        ++ nodecnt , L[nodecnt] = R[nodecnt] = 0;
        cnt[nodecnt] = 1 , key[nodecnt] = x, sum[nodecnt] = x;
        return nodecnt;
    }
    int copynode(int A) {
        if (!A) return 0;
        ++ nodecnt , L[nodecnt] = L[A] , R[nodecnt] = R[A];
        cnt[nodecnt] = cnt[A] , key[nodecnt] = key[A], sum[nodecnt] = sum[A];
        if (nodecnt == 5000000 &mdash; 100) {
          printf("TREAP\n");
          exit(0);
        }
        return nodecnt;
    }
    void pushup(int x) {
        cnt[x] = 1;
        sum[x] = key[x];
        if (L[x]) {
          cnt[x] += cnt[L[x]];
          sum[x] = (sum[x] + sum[L[x]]) % MOD;
        }
        if (R[x]) {
          cnt[x] += cnt[R[x]];
          sum[x] = (sum[x] + sum[R[x]]) % MOD;
        }
    }
    void merge(int& p , int x , int y) {
        if (!x || !y) {
            p = 0;
            if (x) p = copynode(x);
            if (y) p = copynode(y);
        }
        else if ( hey(x , y) ) {
            p = copynode(x);
            merge(R[p] , R[x] , y) , pushup(p);
        }
        else {
            p = copynode(y);
            merge(L[p] , x , L[y]) , pushup(p);
        }
    }
    void split(int p , int& x , int& y , int size) {
        if (!size) {
             x = 0 , y = copynode(p);
             return;
        }
        if (cnt[L[p]] >= size) {
            y = copynode(p);
            split(L[p] , x , L[y] , size) , pushup(y);
        }
        else {
            x = copynode(p);
            split(R[p] , R[x] , y , size &mdash; cnt[L[p]] &mdash; 1) , pushup(x);
        }
    }
    void print(int p) {
        if (L[p]) print(L[p]);
        printf("%d ", key[p]);
        if (R[p]) print(R[p]);
    }
};
Treap T;
char s[10];

int main(void) {
  int n;
  scanf("%d", &n);
  int version = 0;
  REP(i, n) {
    int x;
    scanf("%d", &x);
    root[++version] = T.newnode(x);
  }

  int q;
  scanf("%d", &q);
  REP(i, q) {
    if (version >= 300005 &mdash; 50) {
      printf("TREAP2\n");
      exit(0);
    }
    scanf("%s", &s);
    if (s[0] == 'm') {
      int x,y;
      scanf("%d%d", &x, &y);
      T.merge(root[++version], root[x], root[y]);
      printf("%d\n", T.sum[root[version]]);
    }

    if (s[0] == 'h') {
      int x;
      scanf("%d", &x);
      int v1 = ++version;
      int v2 = ++version;
      T.split(root[x], root[v1], root[v2], 1);
      printf("%d\n%d\n", T.sum[root[v1]], T.sum[root[v2]]);
    }

    if (s[0] == 't') {
      int x;
      scanf("%d", &x);
      int v1 = ++version;
      int v2 = ++version;
      T.split(root[x], root[v1], root[v2], T.cnt[root[x]] - 1);
      printf("%d\n%d\n", T.sum[root[v1]], T.sum[root[v2]]);
    }
  }
}

Any ideas how to improve it?

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

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

Auto comment: topic has been updated by stostap (previous revision, new revision, compare).

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

UPD: sorry i got the problem wrong.

scarped until I get a new solution :P

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

    As far as I understood when you do head/tail operation you also need to keep the previous list and then add two more lists. How do you handle this?

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

I didn't get what you meant by "But this fails as for every query it creates at least Log new nodes". In fact you cannot do a persistent treap in complexity better than , because for each merge or split you create new nodes.

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

Auto comment: topic has been updated by stostap (previous revision, new revision, compare).

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

Auto comment: topic has been updated by stostap (previous revision, new revision, compare).

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

What do you mean by "it fails"? Wrong Answer, Time Limit Exceeded, Memory Limit Exceeded, Runtime Error? Maybe something even more specific?

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

Auto comment: topic has been updated by stostap (previous revision, new revision, compare).

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

I believe it's near to impossible to solve this problem with a simple persistent treap. Trap here is that depth of the tree is , where n is the number of all elements in the tree, which can be doubled with a single operation. Consider the following test case:

  1. There is only a single list initially.
  2. One performs 5·104 merge operations, each of which doubles the largest list.
  3. This results in a list with 25·104 elements, e.g. a tree of depth  ≈ 5·104 (yes, I know that writing such big-O is meaningless from asymptotical analysis' point of view, but I believe my idea should be understandable).
  4. We perform 5·104 head operations on that largest list, each operation creates  ≈ 5·104 new nodes.

That sums up to  ≈ 2.5·109 new nodes which is both TL and ML regardless of any implementation details.

Hint: note that you actually cannot split the list at arbitrary point, you can only chop few of its first/last elements. Then create a smarter approach (which will still use persistent treap, though).

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

    Yes, I know that depth is a problem. My main observation is that we could "cache" some vertex, instead of creating a new one.

    Obvious one is a vertex with left or right result of head/tail. Now thinking about what will be appropriate "hash" for a vertex in treap.

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

      Storing just one vertex doesn't help you as you cannot recalculate that when cutting head/tail off.

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

        hm, I just crazy idea not performing actual splitting for head/tail, but just have 2 counters — cnt_left_cur & cnt_right_cut.

        When head/tail query comes — just make 1 split & 1 merge without creating new nodes (in-place) in actual tree — this shouldn't change a tree.

        When merge comes — make 2 splits (from head and tail) and merge results.

        This is trick for head/tail queries. But I can't find anything for merge :(

        UPD:

        OK, for merge we could not merge them actually, but just hold that this treap constist of T1 & T2. Then when cnt_left_cut > T1.cnt totally forgot about T1, and working only with pair(T2, 0). Similar for cnt_right_cur