Solving 977C - Less or Equal I stumbled over a TLE:
After digging into this I found out that the code gets accepted if the array is expanded by just one element.
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:
- https://www.geeksforgeeks.org/java-handling-tle-while-using-arrays-sort-function/
- https://www.geeksforgeeks.org/when-does-the-worst-case-of-quicksort-occur/
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.
Just shuffle the array before sorting. That'd remove "TLE" if your logic is correct.
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.
Note that the C++
std::sortis usually quicksort but it's a variation that runs in $$$O(n \log n)$$$ in the worst case.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.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.