DPR's blog

Java problem : Submissions getting TLE even after using optimal solution and fast io
By DPR, history, 4 years ago, In English

PROBLEM : 1538C - Количество пар

119286813 -> my submission

119286794 -> some guy's java submission which got accepted

I fail to understand why my submission is failing when is has the exact same logic as the submission which got accepted.

I tried to make it work, but nothing seems to work.

I guess i'll have to say fuck off to java and use C++, because this is just demoralizing.

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

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

Arrays.sort() can be n^2 if you make the right test case.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Well, then why did the second submission get accepted? Both of them used Arrays.sort()

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

      Arrays.sort() for primitives uses quick sort which is O(n^2) worst case. For array of objects (in this case Long[]), Arrays.sort() uses merge sort which is O(nlogn) worst case.

      → Reply