insane_banda's blog

Two almost same solution in java one gets AC and another one gets TLE??
By insane_banda, history, 3 years ago, In English

So I just found out that my solution which is almost same as this one gets TLE on test case 8 while latter got AC.

I can't figure-out why this happened?

Problem link -> C.Save More Mice

Solution:

It turns out that Arrays.sort() in java uses Quicksort which has worst time complexity of O(n^2) and Collections.sort() uses that has time complexity of O(nlogn).

refer to this article for more information.

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

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

Almost same != same

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

    When I used Collections.sort() in place of Arrays.sort() I got AC too. Any idea why?

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

      Yup, arrays.sort() is broken, and it's a pretty known fact in CF community, so it's pretty likely that every problem solved with java gets the test case that pushes sort() it into the TLE limit, either by strong pretests, or by being hacked by someone else.

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

It's because of Arrays.sort which can run in quadratic time for some inputs.

→ Reply