Question: When to avoid square root decomposition?
Разница между en1 и en2, 0 символ(ов) изменены
Are there any good rules of thumb on when a square root decomposition will be too slow? I suspect if we have an interval of length $10^5$ and $3 \times 10^5$ queries a square root decomposition is too slow but this is only based on my attempts to solve http://codeforces.me/problemset/problem/765/F with a square root decomposition where I calculated the complexity of my algorithm to be $O(Q\sqrt{N} \log N)$ and exceeding the time limit. In general if you are given an interval of length $N$ and $Q$ queries what sort of values of $Q\sqrt{N}$ do you want in order to be confident that a square root decomposition will pass the time constraint? Also are there standard limits used in Codeforces deliberately set to prevent square root decomposition based approaches?  ↵

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский usernameson 2017-05-02 18:27:03 0 (published)
en1 Английский usernameson 2017-05-02 18:25:44 822 Initial revision (saved to drafts)