Блог пользователя bharatkulratan

Автор bharatkulratan, 12 лет назад, По-английски

http://mirror.codeforces.com/contest/221/submission/2083431 This link is for solution of Problem C of Codeforces Round #136 (Div. 2). Problem statement: http://mirror.codeforces.com/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.

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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?

»
12 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Sort made O(n^2) operations.

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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