Please see this
Yesterday was Starters 173 (Rated upto < 2700) I am talking about problem- https://www.codechef.com/problems/MINOVER?tab=statement
This was 3rd problem called Overwrite
I couldn't solve this during the contest due to panic and pressure, today I tried looking into it deeply. These are my findings -
1) Correct Soln ( This is most voted ) — https://www.codechef.com/viewsolution/1132142555
Verdict- Accepted
2) I copy pasted same code(after contest) — https://www.codechef.com/viewsolution/1132570276
Verdict — TLE
How did possibly the same codes worked differently? The approach used and time complexity is same in my code too
https://www.codechef.com/viewsolution/1132226217 (This was during contest again tle)
Need feedback from the community on this issue.
Edit: found the submission O(n+m)
Link- https://www.codechef.com/viewsolution/1132254669
Complexity of problematic code is O( (n-m)*m) (i hoped that it might work)
Edit: 2
Keep upvoting downvoting, I don't care, you cannot change the fact that it is rare. That being said, my main intention was to change test cases such that these tweaks don't happen. I will keep this post for future users to see this.
0.98s/1.00s runtime is too close and will give AC or TLE on different submissions, based on how "lucky" you are. Why? Because there is no guarantee that it will run with the exact same time every time, because computers don't work like that.
Also The solution here is not the expected solution for this problem. It's supposed to be solved with O(n + m) time complexity. The solution you are referring to has O(n * m) time complexity.
you are right
Edit: found the submission O(n+m)
Link- https://www.codechef.com/viewsolution/1132254669
Complexity of problematic code is O( (n-m)*m) (i hoped that it might work)
But still it feels bad with such compiler level inconsistencies
Replying to "But still it feels bad with such compiler level inconsistencies": If we wanna be very specific, it even goes deeper than that. Even a simple CPU instruction will have some +/- inconsistencies in the time it takes to execute. That is completely normal, and not anything to "feel bad" about. In fact, that's why you should write an efficient solution, to not have to "squeeze in" the time limit with some other inefficient solution.