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

Optimizing Sqrt Decomposition.
Автор ay2306, история, 6 лет назад, По-английски

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

»
6 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
  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.
→ Ответить
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    can you explain point 2, please?

    → Ответить
    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить
»
6 лет назад, # |
← Rev. 3   Проголосовать: нравится +17 Проголосовать: не нравится

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 :)

→ Ответить