Блог пользователя Mhammad1

TLE with algorithm O(q * sqrt(n)) Where q = 10^5, n = 10^5?
Автор Mhammad1, история, 9 лет назад, По-английски

I'm trying to solve this problem:

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

My submission:

http://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 лет назад, # |
  Проголосовать: нравится +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 лет назад, # ^ |
      Проголосовать: нравится 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 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

→ Ответить
»
9 лет назад, # |
← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

Kinda obvious fix — picking proper constant for decomposition: 12011652

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

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 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 лет назад, # ^ |
        Проголосовать: нравится +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 лет назад, # |
  Проголосовать: нравится 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.

→ Ответить