MZuenni's blog

Problem: Array Stabilization
By MZuenni, history, 6 years ago, In English

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
  • Vote: I like it
  • +32
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks!

→ Reply
»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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). :(

→ Reply