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)
But still it feels bad with such compiler level inconsistencies
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
Auto comment: topic has been updated by Resorcinol (previous revision, new revision, compare).