Increase the chance of a random algorithm passing by abusing TLE verdict on Codeforces

Revision en1, by nikolapesic2802, 2020-06-14 15:28:30

Hello Codeforces!

I want to tell you about a little trick I discovered during Codeforces Round #649, and more specifically, while solving problem E - X-OR.

During the contest, I made a random solution that doesn't have the greatest of chances to pass on it's own. The problem was that it used too many queries when it gets unlucky with random index selection. In my next submission, I added a counter for the number of queries, and a while(true) loop if it exceeds the number of queries.

By doing this, the verdict will be Time Limit Exceeded and not Wrong Answer. Because of how Codeforces works, when a code gets TLE, it will rerun the code several times to see if the code is on the edge of the time limit. By doing this you increase the chances of your code passing significantly! Without this while loop, my code passed 0 out of 10 times, and with it, it passed 5 out of 5 times!

I'm not sure how useful this actually is, but I found it interesting so I'm sharing it, enjoy!

Tags #randomisation, time limit exceeded

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English nikolapesic2802 2020-06-14 15:28:30 1288 Initial revision (published)