Hi,

I was playing one of the contests from Opentrains today, but system was very unreliable:

• I saw a lot of times result "Check failed"

• When I sent the same solution, but different languages, I got a few times "Check failed" and once "AC"

• The same solution on different attempts get PE18, PE34, PE36 etc.

• When I was trying to submit solution, I got a lot of times "Disk write error (disk full?)" message, and my solution wasn't submitted.

I believe there are problems with Opentrains. Can someone who has access check and fix it?

Thanks!

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?

http://www.spoj.com/problems/TROOPS/

Hi, could you give any hints why dp approach here giving WA?

REP(i, n) {
 int x,y,z;
 scanf("%d%d%d", &x, &y, &z);
 FOR(j, max(1, y - x + 1), y + 1) {
  a[j] = max(a[j], z);
 }
}
int sum = 0;
REP(i, T) {
 sum += a[i];
}

Thanks!

http://acm.timus.ru/problem.aspx?space=1&num=1182

Помогите решить — знаю что dp но не могу придумать как... Спасибо!

Помогите пожалуйста решить задачу когда a i m не взаимно просты.
Для взаимно простых есть статья http://e-maxx.ru/algo/discrete_log где сказаночто алгоритм можно модифицировать ... не придумал как :(((