Optimizing Sqrt Decomposition.

Правка en2, от ay2306, 2018-08-13 19:05:43

I was solving this question on codeforces, and was getting TLE for large test cases. I read a blog about different implementation for compare function on coderfoces and changed my compare function to the third option.

After reading a comment saying that bigger sq can decrease runtime, so decided to give it a try. And it worked, I changed my sq size to 1000 and code was accepted.

What I want to ask is

  1. How size of sq ( = sqrt(n) ) changes runtime?
  2. Should I choose a considerable size myself?
  3. How can I optimize my code as it is just passing by bare minimum of time limit?
Теги sqrt-decomposition, complexity optimization, optimisation

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский ay2306 2018-08-13 19:05:43 57
en1 Английский ay2306 2018-08-13 19:04:35 715 Initial revision (published)