Optimizing Sqrt Decomposition.

Revision en2, by 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?
Tags sqrt-decomposition, complexity optimization, optimisation

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English ay2306 2018-08-13 19:05:43 57
en1 English ay2306 2018-08-13 19:04:35 715 Initial revision (published)