In Codeforces Round #748:
Q3. Save more mice
My code in java got TLE in System testcases (all pretests got passed) coz I used 'int' array instead 'Integer' array, crying in corner:(
Integer arr[n]; (Accepted)
int arr[n]; (TLE)
Now I'm not sure whether I should spend time in figuring this out and seek help on this issue or just ignore it. This is the first time I'm facing this. Like why should it matter??
Don't use Arrays.sort(). It's worst case complexity is O(n*n) (n squared). Use some other method for sorting and int arr[] would work fine.
Using Arrays.sort on arrays of primitives (long/int/double/float/char) uses QuickSort, it's easy to set adversarial cases for this, O(N^2), if not system tests, you'd be the victim of some hacking.
Three ways to go about it:
Use arrays of Integer/Long/Double classes instead of the primitives.
Shuffle the array once before sorting (this kills the adversarial inputs) as QuickSort works fine on randomized cases.
Use Collections/Lists instead. Collections.sort() guarantees O(NLogN) sorting.
Integer A = 10;
Integer B = 10;
A == B (True) (works fine until values up to 128, I believe, but don't do this anyway)
Integer A = 1000;
Integer B = 1000;
A == B (False) (Compares references and will yield false)
A.equals(B) (True) (This is the correct way to compare Integers)
I lost 130 rating points cuz of this in a contest, never gonna forget, lol.