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!
I hope that codeforces will not have tasks that use it in author's solution ;_;
this is genius
Congratulations, now people will abuse it, queues will get longer and longer and solutions that should not pass will. Instead, you could've sent a private message to Mike so that he can fix it.
It's not as op as you think. Your random solution still needs to have a decent chance to pass in order for this to work.
Let's say your solution has a 90% chance to pass. If you only have one chance per test case. It's likely to fail after 10 test cases. But if you have 3 chances (i'm not sure how many times codeforces actually tests the code if it gets tle) per test case, you will have a 99.9% success rate per test, making it unlikely to fail.
But if you have a 20% chance to pass, giving it 3 chances will make it a 50% chance to pass. Which will still fail on tests.
Won't you regret exposing this hack if Mike decides to modify the re-judging thing to handle it? :P
Maybe xD
He can easily be able to make us not able to generate randomized seeds. If Mike made us not able to access current time, and disabled clock() commands and any thing which can cause a randomized seed. As I remember, in Codejam, clock() command is already disabled. Mike can pretty much do the same with a disabled access for external time.
There are no hacks at Codejam so you can't solve this problem like this
You can use the address of a random variable on the heap as a seed. And I think there are other ways too.
Wow, didn't think of that xD. That is a pretty smart idea.
Nice trick, I have used it in a previous contest as well.
72346371
I think one can uphack your solution, but as long as it worked, you should feel happy about it :D
I actually didn't know this trick during the contest and just wrote the while loop as a test to make sure my code used too many queries instead of something else failing.
Only after the contest with some extra testing did I realise that this helped the code get AC.
I was in exactly the same position xD
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
Can you please explain how it will increase chance for code to pass as your code will be rejudjed from the very beginning or am I missing something
Afaik, when your code gets TLE, it will be re-run several times. If you get AC one time, then it counts as AC.
If your code has a probability p of passing, meaning that it will fail with probability 1-p.
Giving it 3 chances instead to pass instead of one will make the code fail only if it fails all 3 times. Which has a probability of (1-p)^3.
So if you run the code x times, the probability of it being correct will be 1-(1-p)^x.
Here umnik explained it in a very good manner
Disclaimer: I may get some technical details wrong, don't quote me on the internal workings of testing systems.
I don't think that we can do anything about this. As far as I understand, Codeforces and many other systems try to run several solutions in parallel at first, but if a solution gets a TL verdict, it is rerun on a separate core in more favorable conditions to see whether it really gets TL or if it is the consequence of being run in not the same conditions as promised by the system. Theoretically, one can get rid of this optimisation, but that would increase the testing queue considerably.
In fact, an argument was made several times, that any rejected-type verdict should be rejudged on a separate core. For example, suppose that you have a "while (!TL()) {search for something, terminate if found}" clause in your code. Then, incorrect time measurement can lead to the cycle terminating too early and you getting a WA verdict, while it could be true that you would get AC without this clause, because you would get TL on the first invocation, but AC on the second one. Similarly, you can get RE because you asserted something, et cetera.