imposter_syndrome's blog

By imposter_syndrome, history, 4 years ago, In English

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

I used MO's algorithm to solve it.

My first approach was this **http://codeforces.com/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.com/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.com/contest/86/submission/21756475 code for some arrays and numbers except answer and ans[N] http://codeforces.com/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.

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

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

I'd say you just got lucky. Your second submission passed in 4928ms out of 5000ms time limit, and 80ms is a very tiny amount. Windows (which is used on Codeforces) has measurement error about 16ms. Running time may fluctuate from time to time. If you resubmit your codes several times, you will probably get different outcomes.

Typically, reference solutions run at least twice as fast as required, so in this problem there is a solution which runs in 2500ms or less.

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

    any suggestion on how to improve my runtime sir? This is general approach for this question I guess?

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

      BTW sometimes using a different value for block size can be beneficial. I used block size as 1000 with fast I/O and it got AC with runtime of 3992 ms.

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

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