insane_banda's blog

By insane_banda, history, 2 weeks 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

»
2 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

Almost same != same

  • »
    »
    2 weeks 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?

    • »
      »
      »
      2 weeks 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.

»
2 weeks 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.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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