Once again I found a topic that is useful, interesting but has very less resources online. Before writing this I did a small survey and surprised that most competitive programmers do not know this algorithm. Its important to learn this, all the red programmers on Codeforces use this effectively in Div 1 C and D problems. There were not any problems on this topic an year and half back, but after that there was a spike! We can expect more problems on this in future contests.
Part of course:
MO’s Algorithm (Query square root decomposition)
- Outline:
- The problem statement
- A simple solution which takes O(N^2)
- Slight modification to above algorithm, still runs in O(N^2)
- MO's algorithm to above problem and its correctness
- Proof for complexity of MO's algorithm – O(sqrt(N) * N)
- Explain where and when we can use above algorithm
- Problems for practice and sample code
Show admin stats