Problem: Array Stabilization
Difference between en2 and en3, changed 0 character(s)
Hello guys, for all those who message me here on codeforces, i cant reply since i have reached my daily message quota...↵

### Now to the Hack for todys Div. 3 B. [problem:1095B]↵
-------------------------------------------------------↵

For those who tried to solve this problem in java and Arrays.sort() and got hacked, you need to know that this method implements a deterministic dual pivot quicksort for primitive types like int. This maybe doesn't sounds bad, but it is! A deterministic quicksort is only on random input data in $\mathcal{O}(n\log n)$, but its worst case behaviour is still $\mathcal{O}(n^2)$. Therefore it is possible to find inputs where you will get TLE (like in my hack).↵

There is a generator for this from [user:dalex,2018-12-27] [generator](https://mirror.codeforces.com/blog/entry/4827), and many problem setters know about this an can build such testcases.↵

There are however many ways to fix this here i will list some examples:↵

- use Integer[] instead of int[]↵
- use Arraylist<Integer> and Collections.sort()↵
- use shuffle the int[] before sorting it

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English MZuenni 2018-12-27 23:47:01 0 (published)
en2 English MZuenni 2018-12-27 23:45:21 221 (saved to drafts)
en1 English MZuenni 2018-12-27 23:36:45 894 Initial revision (published)