__declspec's blog

Hacking Java Arrays.sort
By __declspec, history, 3 years ago, In English

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

  • Vote: I like it
  • +31
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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.
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    I didn't explain this earlier, but the reason Collections.sort uses MergeSort is to make it stable, which is desirable with objects, but not important with primitives, since they can't be distinguished anyway.

    → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    regarding option 1: You can sort in-place (without copying back and forth) using Collection.sort if you use something like this

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

      This doesn't compile for me. Here's the error I get on Java 11 on Codeforces Custom Invocation:

      Error message

      Even if it did compile though, I'm almost positive that this is a massive footgun that nobody should ever use, because it makes you insanely prone to comparing Integer objects with ==, which is massively broken in java.

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

    Is there a generator that can hack long arrays? I seemingly could not find one suitable after some searching. Also why sorting int arrays and long arrays are different?

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
      ← Rev. 4   Vote: I like it +55 Vote: I do not like it

      It looks like the issue here is not that sorting int and long arrays are different, but that the first solution reads into an array of size n+1 rather than n:

              long[] num = new long[n+1];
        for (int i = 1; i <= n; i++) {
            num[i]=in.nextInt();
        }

      To properly hack this, it suffices to modify the generator to print only the last $$$n$$$ numbers of the generated array for $$$n+1$$$.

      → Reply