Блог пользователя 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://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
  • Проголосовать: не нравится

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

→ Ответить