humblefool6996's blog

By humblefool6996, history, 2 years ago, In English

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??

Open to suggestions :)

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

| Write comment?
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

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

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:

  1. Use arrays of Integer/Long/Double classes instead of the primitives.

  2. Shuffle the array once before sorting (this kills the adversarial inputs) as QuickSort works fine on randomized cases.

  3. Use Collections/Lists instead. Collections.sort() guarantees O(NLogN) sorting.

Also