bharatkulratan's blog

What’s the reason for TLE in this code?
By bharatkulratan, 12 years ago, In English

http://codeforces.net/contest/221/submission/2083431 This link is for solution of Problem C of Codeforces Round #136 (Div. 2). Problem statement: http://codeforces.net/contest/221/problem/C

I'm not getting the verdict TIME_LIMIT_EXCEEDED for the solution. If anybody could help me finding the reason behind it.

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

»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Maybe it is because Java's sort() method sometimes can work at O(n^2) time.

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

    But how to overcome this O(n^2) complexity? Do I've to write my own implementation of sort() while it's already available in Java library?

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      I don't know Java well, you can ask people, who write on it or look at their code.

      → Reply
»
12 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Sort made O(n^2) operations.

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

As already said Arrays.sort() in Java at worst case works at O(n^2) time. Just because for primitive types sort() it's qsort with median element (l + r)/2, and as known this algorithm can be hacked with special test. There'are two ways to avoid this problem:
1) you can use array with type Integer. Integer is Object, and sort() for Objects use mergesort, which always works good time.
2) you can write your own qsort or mergesort. This way is better, because Integer uses too much memory, so for using array of Integer you have to spend a lot of precious memory, and because in my own tests I learn that in Java algorithms written by your hands work a bit faster that algorithms we have in library

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

    With some modifications, it got accepted; Modified solution http://codeforces.net/contest/221/submission/2084462 In this I used Integer wrapper class and then used Collections.sort(). As it's basically merge sort so no more TLE :)

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

      Try to use arrays instead of ArrayLists in situations when you can, ArrayList is very slow and for Objects all the more so. You can use Integer[] as easy as int[] :)

      → Reply