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!
Auto comment: topic has been updated by Qualified (previous revision, new revision, compare).
Enjoy getting my upvote.
I got the same issue
TLE https://mirror.codeforces.com/contest/1512/submission/112557462
AC https://mirror.codeforces.com/contest/1512/submission/112593466
Same code, >=800ms difference
If you check the logs, all the TLE submissions were tested on 1512G — 9 and all AC submissions were tested on 1512G — 10. My first bet would be that there was an invalid test in revision 9, and no one noticed that because of a bug in the validator. Then someone reported the bug, the validator got fixed, the invalid test was noticed and removed.
UPD: That sounds like a nice explanation but apparently it's wrong. 5 submissions with exactly the same code, probably running on different invokers. Maybe that happened because of recent hardware upgrade? Or was it software only? Maybe tasks are no longer bound to a single CPU, idk.
The running time of most peoples solutions will not depend on the input. Pretty much all time is spent on the $$$O(m\,\text{log}(m))$$$ precalc (with $$$m = 10^7$$$).
I got a TLE from the rejudge (a PyPy2 solution). A friend of mine also got a TLE (a C++ solution). Also many other solutions that I looked at before the rejudge now run > 200 ms slower. It is pretty clear that the rejudge messed something up.
It's not just that rejudge, it looks like the system became less stable as a whole.
Bump