Unusually drastic runtime difference for same code

Правка en2, от Qualified, 2021-04-11 00:54:56

There was some problem with the validator on problems A and G in the recent Div 3 and invalid hacks were considered valid and a lot of solutions got "hacked" because of that. After fixing the issue, the solutions have been rejudged and some AC solutions on G got TLE after being rejudged. But apparently, its not only happening with the submissions to the problems on the recent Div 3, its happening everywhere.

This has been brought to my attention by magnus.hegdahl who submitted 2 submissions https://mirror.codeforces.com/contest/1512/submission/112567753 https://mirror.codeforces.com/contest/1512/submission/112578347
Now if you compare these two codes, the only difference is that the second submission has this line

#pragma Voodoo magic("superfast")

which obviously does nothing. Now look at the execution time. One is TLE, the other is AC with 160 ms to spare. This is very weird. Usually if you submit the same code, the difference is at most 60 ms not this drastic from TLE to AC.

Second case is form Nika_Tamliani who also has the same case. https://mirror.codeforces.com/contest/1512/submission/112584737 https://mirror.codeforces.com/contest/1512/submission/112502297 these two submissions. First one is AC in 1731 ms and second is again TLE. Like before, the submissions are the same except for a comment which obviously shouldn't change the execution time by this much.

Now another case from galen_colin who has these 3 submissions which are also exactly the same https://mirror.codeforces.com/contest/1512/submission/112578130 https://mirror.codeforces.com/contest/1512/submission/112578058 https://mirror.codeforces.com/contest/1512/submission/112503702. First one is AC in 1357 ms, second one is AC in 1840 ms, and third is TLE. All are EXACT same, maybe some comment changes or something but everything is the same. The difference is HUGE, 1357 to 2000 ms TLE? C'mon what is this? Can anyone explain this? It seems very peculiar and strange.

Last case is yet again galen_colin who took TripleM5da's solution after contest and resubmitted it, adding a comment at the top. https://mirror.codeforces.com/contest/1512/submission/112585380 galen_colin's submission https://mirror.codeforces.com/contest/1512/submission/112482209 and TripleM5da's submission. Galen's submission was out of contest while DeadPillow's submission was in contest. Again, the execution time is drastically different. Around 600 ms different.

But it seems like that this error doesn't only occur on the recent Div 3. Again we look at galen_colin's submissions https://mirror.codeforces.com/contest/286/submission/112584630 https://mirror.codeforces.com/contest/286/submission/112584865. As you can see, these problems aren't from the recent Div 3 and were from Round 176 Div 1. The difference is also very drastic, more than 400 ms.

MikeMirzayanov please take a look into this issue.

Thanks to SlavicG for helping me develop the introduction!

Теги plsfixsir, issue

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский Qualified 2021-04-11 00:54:56 38 Tiny change: ' 400 ms.\n\n<br>\n\n' -> ' 400 ms.\n<br>\n\n'
en1 Английский Qualified 2021-04-11 00:49:21 3150 Initial revision (published)