humblefool6996's blog

By humblefool6996, history, 11 days 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

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I also faced the same when i checked this.....

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

java sucks bro :|

»
11 days 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.

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks man, I just saw the GFG article on getting TLE using Arrays.sort()

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Use C++ it's very easy to convert.

»
11 days 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