ay2306's blog

Optimizing Sqrt Decomposition.
By ay2306, history, 6 years ago, In English

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?
  • Vote: I like it
  • -4
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +2 Vote: I do not like it
  1. You can do it by trial-and-error method. There’s a command in Linux “time” which shows you how long did your program worked. For example if your program’s name is test_program you can measure time on Linux by “time ./test_program < test.in > test.out” where test.in is an input. This way you can try multiple square roots on a big test and check out which is the most optimal and therefore try to figure out the best way to set the square root.
  2. Operation “divide” is a little slow. You can try to preprocess all of the dividings (since divisor is constant) and just refere to preprocessed results. This may save a couple of milliseconds.
→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you explain point 2, please?

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      In the input you have n integers and all of them need to be divided by s (a is square root of n, you calculate it once and it remains constant for the rest of the program) so you can have another another array ndiv[n] which stores every element of the input divided by s. If numbers are too big you can just remember which element of an array you use (in comparator change a for arr[a]). Because of this you don’t have to use operation divide nlogn times but just n.

      → Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it +17 Vote: I do not like it

3 — You should be able to save a lot of time just by using '\n' instead of endl to output the result of your queries, as there's no need to flush the output. This should save you enough time to be decently far from the TL :)

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thank you, time reduced to about 80% of the time limit.

    → Reply