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

Автор imposter_syndrome, история, 6 лет назад, По-английски

Hi Everyone, i have been seeing this for some days now on codeforces. In yesterday's educational round, I submitted problem D with https://codeforces.net/contest/1107/submission/49013323 solution. Later I realized that it takes minimum 5040*5040*60 operations in worst case. After contest, i tried hacking my solution but it passed successfully. Also I think testcase 20 is having same worst case input (all 0's and last rows last element if say 1), but it passes there in 732 ms. In my local env it takes more than 4s for this to pass.

Also in CF#534, I tried hacking this O(n^2) solution https://codeforces.net/contest/1104/submission/48743647, which was doing more than 10^9 operation on worst case (ababa....aa..bababababa string). But it passed in 640 ms. From my understanding it takes 1s for approx 10^8 operations.

Has codeforces upgraded there testing servers or I am missing something here?

Полный текст и комментарии »

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

Автор imposter_syndrome, история, 8 лет назад, По-английски

Hello folks! I am new to codeforces and this was my first problem. I was trying powerful arrays http://codeforces.net/problemset/problem/86/D problem.

I used MO's algorithm to solve it.

My first approach was this **http://codeforces.net/contest/86/submission/24070204**

But this got TLE on test case 43. Now when I made a different function checkAns(); in my next submission http://codeforces.net/contest/86/submission/24070298 , it got AC..

All I changed was I put

L=queries[i].L;
    R=queries[i].R;

    while(currentL<L){
       del(currentL);
       currentL++;
    };
    while(currentL>L){
       add(currentL-1);
       currentL--;
    };

    while(currentR<R){
       add(currentR+1);
       currentR++;
    };
    while(currentR>R){
       del(currentR);
       currentR--;
    };

this part of my code in a separate function checkAns(i); I am not getting how this got AC if earlier one was getting TLE. Also isn't function call increases time taken?? Please mention if there is something different on codeforces' platform.

Thanks in advance :)

EDIT:: I submitted different forms of my code for around 20 times in this question. What I saw is that time taken in this question changes abruptly even on subtle changes in code.

For example I changed ll to int in http://codeforces.net/contest/86/submission/21756475 code for some arrays and numbers except answer and ans[N] http://codeforces.net/contest/86/submission/24079499 and it got AC.

When I was doing it, I removed #include <bits/stdc++.h> from my code and time reduced to 2240 from 3630 ms. I think it takes pretty neat and to the point code at Codeforces otherwise these things shouldn't matter.

Полный текст и комментарии »

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