CandidFlakes's blog

Why am i not getting TLE?
By CandidFlakes, history, 11 months ago, In English

I solved this question. Here is my submission 214189574. Now suppose, we have number of days, m = 50000 and the total number of participants = 50000(maximum limit) and suppose that an answer exists. So, the answer would be something like a worst case series like 50000 participants for day 1, 49999 participants for day 2, 49998 participants for day 3,......, 1 participants for day 50000. Then, the total number of operations performed in total days = (50000/2)*(50000+1)=1250025000 operations and as a thumb rule I remember that modern computers can perform 10^8 operations/second. So, it should take 12.5 seconds but my code is running within the 2 second time constraint. Why is this happening? Why am I not getting a TLE error?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by CandidFlakes (previous revision, new revision, compare).

→ Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In the question, the last line under the Input heading states: It is guaranteed that the sum of ni over all blocks of all test cases does not exceed 50000. This guarantees that the sum of participants can't be over 50000 thus the example you have taken for the worst case is not a valid test case as it sum is (50000/2)*(50000+1)=1250025000.

→ Reply