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

Автор MZuenni, история, 6 лет назад, По-английски

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. 1095B - Array Stabilization


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 , but its worst case behaviour is still . Therefore it is possible to find inputs where you will get TLE (like in my hack).

There is a generator for this from dalex generator, 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 and Collections.sort()
  • use shuffle the int[] before sorting it
  • Проголосовать: нравится
  • +32
  • Проголосовать: не нравится

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

Auto comment: topic has been updated by MZuenni (previous revision, new revision, compare).

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

Thanks!

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

In fact, I make such tests, usually. But in this round we decided to increase the constraints of this problem right before the round because of some changes in the problemset and I forgot that it can be solved using sort (and forgot about Java). :(