divyam01986's blog

Ayola and Mex-Java Solution accepted when using Integer[] type array but TLE when using int[] array.Why?
By divyam01986, history, 10 years ago, In English

For this problem the solution is acceptable when an Integer[] array is used but not when the same algorithm is used with an int[] array. Why? Problem URL:http://www.codeforces.com/problemset/problem/682/B TLE Solution:http://www.codeforces.com/contest/682/submission/19309219 Accepted Solution: http://www.codeforces.com/contest/682/submission/19309197

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
10 years ago, hide # |
← Rev. 2  
Vote: I like it +8 Vote: I do not like it

Because Arrays.sort() with int[] is using QuickSort that is O(N^2) at worst case.

Arrays.sort() with Integer[] is using MergeSort that is O(N*log(N)) at worst case.

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

    Thank you for the clarification. I will remember this.

    → Reply
    • »
      »
      »
      10 years ago, hide # ^ |
       
      Vote: I like it +4 Vote: I do not like it

      This bug should actually be fixed in some version of Java, afaik. You can also apply random shuffle to the array before sorting and it should help with anti-quicksort tests.

      → Reply