ZhassanB's blog

Codeforces Round 358, div2, problem B
By ZhassanB, history, 8 years ago, In English

Greetings! My solution to the problem B in Codeforces Round 358 div2 edition, surprisingly failed at 105 th test with verdict 'time limit exceeded'. My code was written in Java, and simply run at O(n) time. I have tried many times by changing Scanner to BufferedReader, but still cannot realize the reason why it cannot pass the time limit. Here is my code. Can somebody guess the reason of failure?

P.S It is not because of Scanner and not because of java compiler version. Moreover I have checked with generated input in my computer and it works fine in about 100 to 250 ms.

  • Vote: I like it
  • +9
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
8 years ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

Check this comment.

Arrays.sort could have quadratic time complexity for specific input cases, since it's a variant of quick sort. If you use merge sort (e.g., link ) it should work.

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

Quoted from MedoN11

Java uses Quick sort for primitive type sorting, and merge sort for Object Sorting.

Quick sort runs in O(N^2) in the worst case, so that alone would TLE your solution. ( Also this does not occur in every problem, sometimes random test cases happen to do that, or the author does it on purpose).

Alternatively, a nice strategy is to shuffle the array before you sort, or declare it as Integer/Long instead of int/long, that way it becomes an Object and runs in NLogN.

→ Reply