Perhaps today and/or tomorrow due to a power outage there may be disruptions in the work of Codeforces and Polygon. Please do not plan any important events during this time. If there are details or the exact time, we will definitely publish them. ×

stostap's blog

By stostap, history, 12 months ago, In English

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!

Read more »

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

By stostap, history, 4 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?

Read more »

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

By stostap, history, 5 years ago, In English

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!

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By stostap, 10 years ago, In English
Why I can't watch my code for submissions and tests?

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By stostap, 10 years ago, In English
Can anyone explain me solution with interval tree? or any other solution?

P.S. I understand Russian

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By stostap, 10 years ago, In English
Please, help. Give me some hints ...

Read more »

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

By stostap, 10 years ago, In English
Task C.
I know solution with O(n * 2 ^ n). Why it is working with n = 24? n * 2 ^ n = 402653184

Task D.
I know that this task is for circle intersection. Who can give me more hint's?

Task E.
I have some ideas about Grey's code. But can't find good solution. Can someboby help me?

Thanks :)

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By stostap, 10 years ago, In English
How I can download big input files from this system? 

Read more »

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