Блог пользователя EigenFunk

Автор EigenFunk, история, 4 года назад, По-английски

Solving 977C - Less or Equal I stumbled over a TLE:

Submission: 80761653

After digging into this I found out that the code gets accepted if the array is expanded by just one element.

Submission: 80762181

Ok, so when sorting an array the time needed for sorting obviously depends on the size of the array, but I'm really surprised to see that increasing the size by one might make the difference between '218ms' or TLE.

I did some local tests, there are some variations but not that significant.

So maybe a layer 8 problem? Am I missing something?

Edit: Not surprising others have written about this in more detail:

Even here by Flatfoot

I think I knew that sorting algorithms have best- and worst-case behaviors. It's just that I'm still blown away that corner cases are so close to 'average' behavior. And still I don't see a pattern which would have signaled this.

  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Just shuffle the array before sorting. That'd remove "TLE" if your logic is correct.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +7 Проголосовать: не нравится

Not a Java programmer, but have heard multiple times that Arrays.sort() uses Quicksort, which works in $$$O(n^2)$$$ time in the worst case. Looking at test 6, it seems that it was specifically designed to hack Java's Quicksort.

As the performance of Quicksort largely depends on the initial order of the elements, just shuffle the array before sorting, as has been previously said.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    Note that the C++ std::sort is usually quicksort but it's a variation that runs in $$$O(n \log n)$$$ in the worst case.

»
4 года назад, # |
Rev. 3   Проголосовать: нравится +8 Проголосовать: не нравится

Or you can use object array like Integer[] arr = new Integer[] I heard that object array uses TimSort which is NlogN in Average.

Primitive array uses quick sort which is O(n^2) in worst case.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Forget about Java: Arrays.sort(a); Answer to your second question. Does Size matters? Not initially. but yeah after few year. xD

For the first question, To be exact, Java uses Dual Pivot Quick Sort. You should always avoid Arrays.sort(a) or try shuffling array before using it.