repeating's blog

Time_Limit_Exceeded !!
By repeating, history, 8 years ago, In English

Hello

Today I tried to solve problem 327E - Идем по оси , but I faced a problem with Time_limit

I kept getting TLE on tests between 7->10 , then I submitted my friend's solution 24099917 which got ACC

but I got TLE on test 11 24109427 , and when I test it on CUSTOM INVOCATION it pass the test with 1372 MS

P.S.:the problem time_limit is 3000 MS

So can anybody help me and tell me the reason of getting TLE

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

»
8 years ago, # |
  Vote: I like it -12 Vote: I do not like it

As you can see in the blue area of the problem, the time will be multiplied by 2. So actually, the time cost is 2744 ms. And the 250 ms difference is so little that you get TLE. Your friend's solution runs 2800 ms(actually 1400 ms), which is very close to the time limit. So it's not surprising that you get TLE while your friend get AC.

BTW: The time complexity of your friend's solution is O(2^n*n)=O(4e8). The Codeforces grader can run about 1e8 in 1000 ms, so you'd better improve your (friend's) algorithm. :)

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    So the same code sometimes gets AC and sometimes doesn't ???

    What kind of logic is that ???

    Do they roll the dice on the Verdict if the Execution Time is very close to the TL ???

    What if that happened in a contest where solution with the same (or almost the same) time complexity got different Verdicts ???

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +24 Vote: I do not like it

      You know, the windows timing sever is very inaccurate, so it will have a difference of about -50ms — 50ms, so it's just your fault that you haven't designed a algorithm fast enough. It's also not rare in a contest that one solution gets TLE while the same one gets AC in a re-submission. There's also a example. In the ACM competition, someone outputs "YES" and "NO" randomly gets AC in about 20 submissions. So if the same code runs differently, it's your fault instead of the Codeforces polygon. You should have designed an algorithm without such problems. And I wonder why so many downvotes :(

      → Reply