| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 161 |
| 5 | -is-this-fft- | 158 |
| 6 | awoo | 157 |
| 7 | adamant | 156 |
| 8 | TheScrasse | 154 |
| 8 | nor | 154 |
| 10 | djm03178 | 153 |
http://codeforces.me/contest/221/submission/2083431 This link is for solution of Problem C of Codeforces Round #136 (Div. 2). Problem statement: http://codeforces.me/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.
Maybe it is because Java's sort() method sometimes can work at O(n^2) time.
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?
I don't know Java well, you can ask people, who write on it or look at their code.
Sort made O(n^2) operations.
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
With some modifications, it got accepted; Modified solution http://codeforces.me/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 :)
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[] :)