sankalp_'s blog

Why is there such a big variation in time?
By sankalp_, history, 7 years ago, In English

I was solving some problems and I found an interesting thing regarding the execution times on the server. If anyone could provide me with an explanation it would be amazing. Thanks :)

Here are the links to the submissions :

1 : 62ms

2 : 30ms

For those who didn't check the submissions here's what happened :

62ms code :

int n;
cin>>n;

cout<<3*n/2<<endl;
return 0;

30ms code :

string str0,str1;
cin>>str0>>str1;

int cnt=0;
str0+="$";
int len=str1.length();
REP(i,len)
    if(str1[i]==str0[cnt])
        ++cnt;

cout<<cnt+1<<endl;

return 0;

}

No matter how I look at it the second code should have more exec time right?

Any help regarding this is highly appreciated.

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

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

I guess resources in the server are shared and sometimes you can get a little more time because of this, I resubmit your first solution and I get the same 30ms as your second solution.

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

    Isn't that a bit unfair?

    I mean the execution time was almost doubled due to sharing and if this happens during contests isn't there a possibility that someone gets a TLE and someone else with a similar code gets AC?

    What if a code doesn't even pass the pretests and some other similar code passes the pretests and gets accepted?

    → Reply
»
7 years ago, # |
  Vote: I like it +24 Vote: I do not like it

  1. The granularity of measurement is ~15ms. You can get only numbers like ~15ms, ~31ms, ~46ms, ~62ms, and so on.

  2. As we see, one can expect some error in measurement. As long as it's only an additive error of up to 30ms, and the time limits for the problems are at least 1000ms, there is not much to worry about. In an event that a solution takes within 30ms of a time limit, it's problematic, yeah. But problem setters generally try to reduce the likelihood of such solutions.

→ Reply