Resorcinol's blog

Codechef's Inconsistency
By Resorcinol, history, 14 months ago, In English

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.

  • Vote: I like it
  • -8
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
14 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
14 months ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

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.

→ Reply
  • »
    »
    14 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      14 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      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.

      → Reply