I exactly implemented the tutorial for the problem G. Hits Different. The solution they gave looks like they have the same time complexity as mine. But still, I get a TLE on test case 2. My Submission
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3690 |
2 | jiangly | 3647 |
3 | Benq | 3581 |
4 | orzdevinwang | 3570 |
5 | Geothermal | 3569 |
5 | cnnfls_csy | 3569 |
7 | Radewoosh | 3509 |
8 | ecnerwala | 3486 |
9 | jqdai0815 | 3474 |
10 | gyh20 | 3447 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | maomao90 | 173 |
2 | awoo | 164 |
3 | adamant | 163 |
4 | TheScrasse | 160 |
5 | nor | 157 |
6 | maroonrk | 156 |
7 | -is-this-fft- | 152 |
8 | Petr | 146 |
8 | orz | 146 |
10 | pajenegod | 145 |
I exactly implemented the tutorial for the problem G. Hits Different. The solution they gave looks like they have the same time complexity as mine. But still, I get a TLE on test case 2. My Submission
Название |
---|
Pass by (const) reference unless you have a reason not to do so.
+1
Did that but still getting a TLE. My Submission
"The solution they gave looks like they have the same time complexity as mine."
I haven't read the problem. However, there is another nested loop in
sum()
. I can't find why they have the same complexity.They did a precomputation of the main algorithm that you are doing every time for every test case. The time complexity for your solution is ~ T * (1500*(1500+1)/2) (considering the nested for loops in
solve()
and the loops insum()
function). So in the worst case, it goes upto ~1.125 * 1e9 number of iterations. What the solution does is it precomputes the main algorithm in ~1.125*1e6 and then for each test case, it is performing an O(1) operation. So in the worst case, it won't exceed 2.5*1e7 which is roughly 2.5sec (if I take 1e7 iterations in one sec).thanks dr. ankan