During Yesterday's EDU round, My solution to D was accepted and during system testing, it got TLE on test case 60. AC during contest : (https://mirror.codeforces.com/contest/1499/submission/110354551)
Now I submitted the same code multiple times after system testing is over, it is getting accepted. AC after system testing : https://mirror.codeforces.com/contest/1499/submission/110419651
So can anyone please tell what can be wrong in this scenario ?
Auto comment: topic has been updated by K_B_G (previous revision, new revision, compare).
same with my submissions....
I got TLE on this submission 110412288 after removing visted vector I got AC on this 110427352. It is because of Visited array
Yes, I am having similar issues. All submissions are almost the same, you can compare. I think that the time limit to this problem is not optimal.
Submission 1 : https://mirror.codeforces.com/contest/1499/submission/110420452
Submission 2 : https://mirror.codeforces.com/contest/1499/submission/110390562
PS: the same code Submission : https://mirror.codeforces.com/contest/1499/submission/110420816 gives tle on test 39 now.
PS (yet again) : The SAME CODE is $$$Accepted$$$ now!!! Solution : https://mirror.codeforces.com/contest/1499/submission/110421153
Just change the way you write $$$2\times 10^7$$$, you will get tle. Solution : https://mirror.codeforces.com/contest/1499/submission/110422095
I have made some minor changes in each submission, so that Codeforces allows me to resubmit.
Admins please look into this issue, to either increase the time limit of this problem or take some other steps you might find suitable in this case.
To all the people that passed with 1996ms, you just got extremely lucky, nothing more than that. Your solutions should have failed. Extra log factor adds 500ms to the execution time in this case, and that ruins the purpose of this problem, it's a D2D, all the details matter. If you really want to make it fair — than take the time limit down to 1.9s, and the lucky ones will get removed. There are dozen of non-optimal implementations which will pass if you increase TL from 2 to 2.2-2.3 seconds. Come on, it's just one contest, don't blame tests for your mistakes.
.
I'm sorry, but I don't understand random gibberish. Rephrase your sentence/translate it to English so we all understand you. :)
Blaming tests? It's the time limit I said for. And yes, even if the time limit is decreased it is completely okay, at least those lucky ones get filtered out.
I don't know the specifics of why it happened, but I think it's something to do with a bit of random variance when running a program.
Yep, that happens, its just that every time you run a program it won't run in exactly the same time, there will always be minor fluctuations in runtime, for example this submission ran in around 1980 ms during the contest but I figured it would probably TLE out in system test so I optimised it a bit and submitted it again here which ran in around 1700ms during the contest, It barely passed on system test with 1996ms :/
So yeah, optimise as much as you can.
there are many people who got accepted and have 1950ms or above time limit during contest.
Yes, as I said runtime fluctuates by a bit, so for a program that should take 1000ms, sometimes it may take 1050ms and sometimes it may also run in 950ms, as a result some people's solution might TLE out while some of those solution may also pass due to those minor fluctuation even though they had roughly the same runtime during the contest, as such we can't really do much about this and therefore our best option is to just optimize as best as we can.
yes i am completely agree with you but this is biased.
Randomness is not being biased. Optimize your solution so you don't have to rely on randomness to get an AC.
Dude what do you mean? this is completely random.
Yeah my solution also ran in 1996 ms
But Why do we have such random run time despite having a same time complexity and same constant factor(i guess)?
The truth is you don't. If you remove vis array from solution. You get 1600ms runtime, it's your fault, it's not needed. Were you able to estimate 2e7 log 2e7 takes about 0.5s to execute => your solution is nowhere near optimal, because you do useless calculations. Come on, it's a D2D, what do you expect, writing a 0.5s random for loop and expecting to pass? 110425446
Yeah, that makes sense.
Thanks for pointing that out
same issue with me
tle:110372505
now passed: 110421066
Same issue TLE: 110405479 AC: 110422060
I think sometimes if the time limit is so strict they should rejudge the solutions by increasing the time limit by small amount
No need to rejudge, there was more than enough time for solutions to pass. It's your fault choosing to use unoptimal strategies. Simplest sieve passes all the tests in about ~1.3s. Take a look at icecuber's submission and you'll see what I'm talking about. It's the same as saying, please increase the time limit I used map instead of unordered_map.
Same issue https://mirror.codeforces.com/contest/1499/submission/110380734 and https://mirror.codeforces.com/contest/1499/submission/110424412. I hope admins look into this.
Your factorization is not optimal — therefore you waste ~500ms. It can be all done in one for loop, no need for another log factor. You add n log n execution time in the worst case, which is ~2e8 operations, these solutions should be intended to fail, when you add such a large factor for no reason.
That makes sense. Thanks for pointing it out.
I was able to get the runtime close to 1000 ms with some precomputation with sieves. Can anyone help optimize this any further? I would be very grateful
https://mirror.codeforces.com/contest/1499/submission/110425912
I used linear sieve and my latest solution runs in $$$\textbf{468 ms}$$$.
Same thing happened with me.see this 110380490 and this 110426784.MikeMirzayanov sir these submissions are same.still one passing after sys test and another giving tle during sys test