MO's ( Query-Sqrt Decomposition) Algorithm on Tree

I was trying hard to solve a problem from July Long Challenge and even after one day of thinking i was not able to solve it. So i decided to solve sub-tasks. For solving sub-tasks, i decided to use MO's algo (aka Query-Sqrt Decomposition).

Prerequisite: MO's algorithm, Euler tour technique (ETT).

So, I needed to do queries on edges (weights) of undirected tree. After searching little bit, i found this article on codeforces. It's a good article. I learnt how to do queries on path for a given tree but the problem was to do queries on edges, not vertices.

After thinking for a while, i came up with a solution. I stored the ETT of the tree in a vector and did all the queries on the ETT. In this method we don't need to find LCA. All we need to do is store the position of first occurrence of each element in an array. For doing query between u and v, we need to do query between firstOccurrence(u) to firstOccurrence(v). While doing query, if an edge occurs twice, we need to remove its contribution from answer. It will be more clear from the following example:

Let us find the sum between u and v for the given tree.

 The ETT for the above example is : { 1, 2, 3, 4, 3, 2, 5, 6, 5, 2, 1, 7, 8, 7, 9, 7, 1}
(How?  open this).

Code for finding ETT:


Now for example i want to do query between 6 to 9.

(Assuming 0-based index)

L = firstOccurrence(6)
R = firstOccurrence(9)

so L = 7  and R = 14

{ 1, 2, 3, 4, 3, 2, 5, 6, 5, 2, 1, 7, 8, 7, 9, 7, 1,}

The answer is (6 -> 5) + (5 -> 2)+ (2 -> 1) + (1 -> 7) + (7 -> 8) -  (8 -> 7) + (7 -> 9), i.e., 8+2+5+4+1-1+6 = 25.
As i mentioned earlier, if an edge comes twice we will delete its contribution to answer, that is why we removed (8->7)'s weight, as it has occurred earlier.

I hope, you guys find it helpful and interesting!

Read More

AGGRCOW - Aggressive cows SOLUTION

AGGRCOW - Aggressive cows is a good question based on Binary Search! (It took me an hour to figure out, how to crack this nut using binary search :P )

My solution's complexity is O(n logn).

If you haven't done a lot of problems based on binary search, then this problem will make you learn something good!

Now let us talk about the question. In the problem statement it is given that N (2 <= N <= 100,000) and
x1,...,xN (0 <= xi <= 1,000,000,000). This makes one thing very obvious that the maximum possible ans is  1,000,000,000 and the minimum possible answer is 1.

We have got our upper and lower limits, and now we have to find the answer, which exist between them.

But the question arises, why binary search? It is very clear that, for a value 'x', if it is not possible to keep all the cows in the stalls with the minimum distance between any two cows as 'x', then it will not be possible for all y > x  , and hence answer<x. This is the point which gives entry to binary search in the scene!

Now, we will do binary search for answer, with i as upper and j as lower limit, mid is the middle element. For each mid we will see if it is possible to fit all the cows in stalls with mid as the minimum distance between any two cows. Further we can decide if we have to search for the answer in the upper or lower half of the mid!

If you find any difficulty in coding part, refer to the following code!

Happy Coding! :) 

Read More