SPOJ ARRAYSUB

SPOJ Problem Set (Classical) 10582. Subarrays

This was also one of the problems I was asked on my recent interview with Google. Problem is a simple one for segment tree based algorithm. The solution basically requires us to maintain a Range Maximum Query (RMQ) algorithm, and I implemented this using segment tree.

Given, there are N items and a window of size K, we have to find the maximum item in each K sized window. First, we insert the first K items in the RMQ, so the segment tree root now knows the maximum item at this stage. Now if you observe you will see, for the (k+1)th item, 1st item will be removed from the tree and (k+1)th item will be inserted. This can be done by inserting (k+1)th item at the position of 1st item. Because for (k+1)th item, 1st item is in the oldest position. And clearly, for each of the next items, we can just insert it in the current oldest position on the K sized window. so (k+1) will be inserted at index 1, (k+2) at 2, (k+3) at 3 ... (2k) at k, (2k+1) at 1, (2k+2) at 2 and so on. So all we need is to keep inserting the items in the RMQ in a circular fashion and each time taking the updated range maximum value.

So, basically the structure of the code is:

for(i = 0; i < k; i++) insert(root, 0, k-1, item[i]);
output Tree[root];
for(; i < n; i++) {
    insert(root, 0, k-1, item[i % k]);
    output Tree[root];
}
// considering item indexes to be 0 based in code
// insert is the function that inserts an item on a specific index in the RMQ tree

So, once you write down the RMQ function insert, you are pretty much done with it. Happy coding!

SPOJ RPAR : Raining Parabolas

6906. Raining Parabolas

Problem Summery

Given an array of n items h_i ( 0≤i<n ), we have to perform an update operation for a given range [i,j] such that, h_x = (h_x + f(x))%M, ( i≤x≤j and f(x) = ax²+bx+c ). We also have to perform a query operation for a range [i,j] such that, result = (h_i + h_i+1 + h_i+2 + … + h_j)%M.

Solution Idea

Solution idea with the help of a segment tree is quite simple. First, we need to observe the types of information we need to store on each node of the tree. As we will be facing range updates, lazy propagation can be utilized, so, we can have three carry variables, namely ca, cb, cc. If we look closely to the update procedure, parts with x² are added together and parts with x are added together and there is another part which are the constants. We can resemble them namely with variables, a, b, c, i.e. a is the variable that holds the sum for x² part, b is the variable that holds the sum for x part and c is the last one that holds the constant part. Also, we can keep the pre-computed values of sum of x² and x on tree node ranges for the ease of calculation.

Now, let’s dissect the update part. Say, on node p (i to j) we already have in a:

a₁x_i² + a₂x_i+1² + a₃x_i+2² + … + a_nx_j²

Now we want to add a new parabola (a, b, c) on this range, as only x² parts will be added here, so the new value of a on this node will be:

(a₁+a)x_i² + (a₂+a)x_i+1² + (a₃+a)x_i+2² + … + (a_n+a)x_j²

So, we can easily see the extra value added with the previous in variable a:

a * (sum of x² in range [i,j])

Similarly, for x part, i.e. variable b we can show the added value is:

b * (sum of x in range [i,j])

And for the constant part, i.e. variable c we can show the added value is:

c * n where n is the size of range [i,j];

So we can perform these updates now using lazy propagation, and query is also done in the similar way, the final result for a range is simply the sum of variable a, b, c from that range. And obviously modulus operations must be handled properly.

Have fun!