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

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

I'm trying to solve this problem:

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

My submission:

http://codeforces.me/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
  • Проголосовать: не нравится

»
11 лет назад, скрыть # |
 
Проголосовать: нравится +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.

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

    → Ответить
»
11 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

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

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

Kinda obvious fix — picking proper constant for decomposition: 12011652

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

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

→ Ответить