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

Hacking Java Arrays.sort
Автор __declspec, история, 5 лет назад, По-английски

Is it possible to hack java's quicksort? I found this generator only capable of hacking int arrays but not long ones.

Unsuccessful hacking attempt (they used Arrays.sort on long array): https://codeforces.me/contest/1671/hacks/798786

Successful hacking attempt (they used Arrays.sort on int array): https://codeforces.me/contest/1671/hacks/798795

  • Проголосовать: нравится
  • +31
  • Проголосовать: не нравится

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

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

→ Ответить
»
5 лет назад, скрыть # |
 
Проголосовать: нравится +21 Проголосовать: не нравится

As a long time java user, yes, it's possible to hack it. You can also hack long, but I think you need a different generator. The source code for the generator is essentially a copy-paste of Java's Arrays.sort method, but built in such a way to make Arrays.sort pick the worst possible pivot each time.

So, what should you do instead?

  • Option 1: Use Collections.sort(). This uses Mergesort instead of QuickSort, which has a worst-case complexity of n*log(n) which is better than the n^2. You can put everything into an ArrayList, sort that, and then copy it back.
  • Option 2: (faster constant factor, my favorite) RuffleSort! You can copy it from any of my submissions, but the idea is to shuffle the array O(n) before sorting it. It's still O(n*log(n)) just like option 1, but it's faster.
  • Option 3: (even faster, but only works when array size is >=5*10^4): Use a radix sort to sort the array in O(2*n) for ints, or O(4*n) for longs using 2^16 buckets. You have to be careful with this one. On problems with 10^4 testcases, you can TLE if your runtime is O(2^16 + n) per testcase, which is easy to miss.
→ Ответить