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.
