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.net/contest/1671/hacks/798786
Successful hacking attempt (they used Arrays.sort
on int
array): https://codeforces.net/contest/1671/hacks/798795
Auto comment: topic has been updated by __declspec (previous revision, new revision, compare).
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?
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.
regarding option 1: You can sort in-place (without copying back and forth) using Collection.sort if you use something like this
This doesn't compile for me. Here's the error I get on Java 11 on Codeforces Custom Invocation:
Invocation failed [COMPILATION_ERROR] Can't compile file: I.java:30: error: cannot inherit from final Array static class IntArray extends Array { ^ I.java:30: error: type Array does not take parameters static class IntArray extends Array { ^ I.java:37: error: method does not override or implement a method from a supertype @Override ^ I.java:42: error: method does not override or implement a method from a supertype @Override ^ I.java:49: error: method does not override or implement a method from a supertype @Override ^ 5 errors File should contain public class named as the file.
===== Used: 0 ms, 0 KB
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.
wut?
1) Array class in not final https://github.com/AlexeyDmitriev/spsl/blob/master/name/admitriev/spsl/collections/array/Array.java 2) The whole point is that you create IntArray, sort it and then throw it away and continue using int[] like this https://github.com/AlexeyDmitriev/spsl/blob/master/name/admitriev/spsl/collections/ArrayUtils.java#L17
Ah, the default one in Java is: java.lang.reflect.Array; Bit confusing that you're making your own, but I suppose it could be made to work, yeah. Or just ruffle ¯\_(ツ)_/¯
Is there a generator that can hack
long
arrays? I seemingly could not find one suitable after some searching. Also why sortingint
arrays andlong
arrays are different?It looks like the issue here is not that sorting
int
andlong
arrays are different, but that the first solution reads into an array of sizen+1
rather thann
:To properly hack this, it suffices to modify the generator to print only the last $$$n$$$ numbers of the generated array for $$$n+1$$$.