Mhammad1's blog

TLE with algorithm O(q * sqrt(n)) Where q = 10^5, n = 10^5?
By Mhammad1, history, 9 years ago, In English

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?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 :)

    → Reply
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

std::list can be very slow. Try replacing it with your own singly-linked list.

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Kinda obvious fix — picking proper constant for decomposition: 12011652

Upd.: This one looks even better — 12011711 :)

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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.

      → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply