MO’s Algorithm (Query square root decomposition)

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 almost none of the Indian programmers knew 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 an year and half back, but from then there is a spike up! We can expect more problems on this in future contests.

1) State a problem
2) Explain a simple solution which takes O(N^2)
3) Slight modification to above algorithm. It still runs in O(N^2)
4) Explain an algorithm to solve above problem and state its correctness
5) Proof for complexity of above algorithm – O(Sqrt(N) * N)
6) Explain where and when we can use above algorithm
7) Problems for practice and sample code

State a problem

Given an array of size N. All elements of array <= N. You need to answer M queries. Each query is of the form L, R. You need to answer the count of values in range [L, R] which are repeated at least 3 times.
Example: Let the array be {1, 2, 3, 1, 1, 2, 1, 2, 3, 1} (zero indexed)
Query: L = 0, R = 4. Answer = 1. Values in the range [L, R] = {1, 2, 3, 1, 1} only 1 is repeated at least 3 times.
Query: L = 1, R = 8. Answer = 2. Values in the range [L, R] = {2, 3, 1, 1, 2, 1, 2, 3} 1 is repeated 3 times and 2 is repeated 3 times. Number of elements repeated at least 3 times = Answer = 2.
Continue reading

When 2 guys talk, its not always about girls/sports ;)

Let me introduce to you my friend Archit Karandikar. I met him at Directi last summer, we were interns, since then we are good friends :). I was quite impressed with his skills. Many of us know that he is awesome at math and programming. Let me tell you, majority of the Indian programming community do not know him only because he does not take part in codechef long contests 😛

archit
Continue reading

Persistent segment trees – Explained with spoj problems

In this post I will introduce the concept of persistent data structures. We shall deal with a couple of problems : COTMKTHNUM

Consider the following question :

Given a linked list, you need to support 2 operations. 1) Update the first x values. 2) Print the linked list after k’th update (k <= number of update operations made till now)

Simple solution is to create a new linked list after each update operation. print it when needed. Let us optimize it for memory.

We are only updating first x elements of the linked list. That means the new linked list will be almost same as previous linked list if x is small. We shall take advantage of this and avoid allocating memory for some elements. We can allocate memory for x elements, store new values in them, then point the next pointer of x’th node of new linked list to (x+1)’th node of previous linked list. This way we allocated only x units of memory per update operation.

Consider the following example.

Initial linked list : 1 2 3 4 5 6 7 8 9 10.
Update 1 : x = 4, new elements : 12 13 14 15
Update 2 : x = 2, new elements : 20 21
Update 3 : x = 6, new elements : 1 2 3 4 5 6
Update 4 : x = 1, new elements : 100

Initial linked list will look like this

head[0]-->[01]-->[02]-->[03]-->[04]-->[05]-->[06]-->[07]-->[08]-->[09]-->[10]

After first update total data will look like this

head[0]-->[01]-->[02]-->[03]-->[04]-->[05]-->[06]-->[07]-->[08]-->[09]-->[10]
                                      /
head[1]-->[12]-->[13]-->[14]-->[15]--'

Continue reading

Heavy Light Decomposition

Long post with lot of explanation, targeting novice. If you are aware of how HLD is useful, skip to “Basic Idea”.

Why a Balanced Binary Tree is good?

Balanced Binary Tree
Balanced Binary Tree

A balanced binary tree with N nodes has a height of log N. This gives us the following properties:

  • You need to visit at most log N nodes to reach root node from any other node
  • You need to visit at most 2 * log N nodes to reach from any node to any other node in the tree

The log factor is always good in the world of competitive programming 🙂

Now, if a balanced binary tree with N nodes is given, then many queries can be done with O( log N ) complexity. Distance of a path, Maximum/Minimum in a path, Maximum contiguous sum etc etc.
Continue reading