By Mhammad1, history, 9 years ago,

I'm trying to solve this problem:

http://mirror.codeforces.com/problemset/problem/455/D

My submission:

http://mirror.codeforces.com/contest/455/submission/12009574

My algorithm runs in O(q * sqrt(n)) so it should pass the test cases. So the question is: what's wrong in my code to make it giving me TLE?

• 0

 » 9 years ago, # |   +1 For n up to 1e5 and linear complexity you won't get TLE but you have no guarantee with O(n * sqrt(n)). Try to run custom invocation with some random input. Maybe constant is big and you need ~5s instead of 4s. Then you can change your code a bit.
•  » » 9 years ago, # ^ |   0 I don't think that the problem with the big of constant, I tried different test cases with worst case and they gave me the answer with the specific time, and the previous test cases my code passed them all with less than 2s.thanks for your help :)
 » 9 years ago, # |   +1 std::list can be very slow. Try replacing it with your own singly-linked list.
 » 9 years ago, # | ← Rev. 2 →   +1 Kinda obvious fix — picking proper constant for decomposition: 12011652Upd.: This one looks even better — 12011711 :)
•  » » 9 years ago, # ^ |   0 Thank you very much, but just a question: Is it needed every time to pick constant for decomposition or it was a special case for this problem?
•  » » » 9 years ago, # ^ |   +1 Basically every decomposition solution does C1 * root + C2 * (N / root) operations. Your goal is to minimize this value; will be best choise only if C1 = C2, but in most cases one part of your solution is slower than other and you need to take a different value of root.
 » 9 years ago, # |   0 Modulo Operator is very slow . Try Replacing from = ((from + lastans - 1) % N) + 1;to from += lastans - 1; if(from >= N){ from -= N; } ++from; Also Wherever you used modulo you should change it to this.