A wrong solution to C2 got accepted: https://codeforces.me/contest/2284/submission/397621024
I submitted the exact same code initially and received a WA. However, when I submitted it again, without making any changes, it got accepted. It doesn't seem fair in competitive programming when the same incorrect code can receive different verdicts on separate submissions.The reason behind this soln getting accepted is the weakness of test cases i think.
UPD--
my concern is not about getting accepted by changing return; to return ; . It was about getting lucky even though the answer is wrong. the solution is correct when the number of times we need to generate random numbers is correct. In this , the number is calculated using wrong probabilities but still the author got lucky and his solution got accepted in the first try. That means the test cases were not strong enough , that's all.
The method used here is absolutely fine but the calculated number of times we need to generate an random number is wrong , i just wanted to flag that mistake but i think you all understood it wrongly.
its so freaking funny, even i tried both of your codes
return; gets AC return ; gets WA lol
lemme check the testcase on which it got WA, and try to run AC solution on that testcase
but yea thats definitely a bug
tf is that judgement(on test 4) "wrong answer You could do shorter though (test case 3291)"
I'm not sure but I think it's just about luck. The solution just tries to generate random values and use the time for seed. So there is no gurantee for same output on every run.
If you use a timestamp+initialized RNG and have a randomized algorithm then you should expect it not to behave the same every time. Maybe weak pretests that you could get AC once but that's all.
i tried same code twice right now, one got AC another got WA!, so u can actually get ac multiple time just by using return; instead of return ;
The reason for AC wasn't changing return; to return ; , It was because the algorithm is randomized, meaning it will randomly give correct answers sometimes and wrong other times irrespective of if you submit the same code multiple times.
cool
yeah, my concern is also that there are not enough strong test cases for this problem to flag this mistake. btw this soln is wrong bcz of using wrong probability of two numbers being co-prime , a solution can exist in this form using random numbers if we use actual probability of two numbers being co-prime and then find the no. of random numbers needed to generate using prob>0.9990 .
Auto comment: topic has been updated by L_ryuzaki_ (previous revision, new revision, compare).