Hello everyone. how i could avoid time limit exceeded in this problem E.Time Limit Exceeded? http://codeforces.com/gym/100676
Hello everyone. how i could avoid time limit exceeded in this problem E.Time Limit Exceeded? http://codeforces.com/gym/100676
# | User | Rating |
---|---|---|
1 | jiangly | 3640 |
2 | Benq | 3593 |
3 | tourist | 3572 |
4 | orzdevinwang | 3561 |
5 | cnnfls_csy | 3539 |
6 | ecnerwala | 3534 |
7 | Radewoosh | 3532 |
8 | gyh20 | 3447 |
9 | Rebelz | 3409 |
10 | Geothermal | 3408 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 173 |
2 | adamant | 164 |
3 | awoo | 161 |
4 | TheScrasse | 160 |
5 | nor | 159 |
6 | maroonrk | 156 |
7 | SecondThread | 152 |
8 | pajenegod | 146 |
9 | BledDest | 144 |
10 | Um_nik | 143 |
Name |
---|
Hello...
This problem solvable using
Binary Search
, but you need to edit something in the algorithm.There is no need to use Binary Search. Two pointers can do step 4 in O(n)
can you show me how we can code it using two pointers
O(n) code
Just keep two pointers P1 and P2, initially both pointing to the first element. If increasing P2 won't cause them to be 32 apart, increase it. If it will cause them to be too far apart, then increase P1.
Each time you increase P1 you can add (P2-P1) before increasing it, and there you go!
Both pointers will travel a total distance of O(N), it is often easy to replace binary with two pointers.
If you want to be super-optimal you could even replace the regular sorting with counting sort, making use of small values, to achieve linear solution for the whole problem :)
code
line 39-43
nothing :/