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://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
↵
### 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://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
