OJ Board

i read the RMQ problem from TC. From the section
http://www.topcoder.com/tc?module=Stati ... cted%20RMQ.


i understand most of it except

It remains now to show how the in-block queries can be made. Note that the length of a block is l = [(log N) / 2], which is quite small. Also, note that A is a binary array. The total number of binary arrays of size l is 2^l=sqrt(N). So, for each binary block of size l we need to lock up in a table P the value for RMQ between every pair of indices. This can be trivially computed in O(sqrt(N)*l^2)=O(N) time and space. To index table P, preprocess the type of each block in A and store it in array T[1, N/l]. The block type is a binary number obtained by replacing -1 with 0 and +1 with 1.



I don't quite get this. Can you please elaborate ?

say we have block like 1 2 3 4 3 4 3 2 1, the +/-1 array would be
1 1 1 1 -1 1 -1 -1 -1, how to calculate the minimum value between 2 and 6.
ie 1 1 -1 1 -1 -1

Can we take any of the -1 values ? Why would any of them be okay ? The LCA of 2 nodes is a single node there is no ambiguity about it.

So we if have some like 1 -1 1 , it is always going to be index 1 ,
how can we guarantee that part ?
how to compute minimum for 1 -1 -1 -1 1 1 1 for the values (0,6)

You misunderstood a bit.
Of course, we find minima in original array, not in +-1 array.
But to find it efficiently, we exploit the fact, that each element a is a[i-1]+-1.
More precisely, we can divide array a[1..N] into blocks of length L=logn/2, and precompute RMQ in each block i between each pair (j,k).
But if we do this naively, then we'll get asymptotic about (N/L) * L^2 = N * L, that is not good enough.
And here we do an interesting trick: note that each block has length L=logn/2, that means that if we replace each block with its mask (got from +-1 representation) and first value of first element in block (because, +-1-representation is not enough to restore the block), than there could be only 2^L = 2^(logn/2) = sqrt(N) different masks.
This means that we don't have to precompute RMQ in each of N/L block, but only is those of them, that have unique masks (here we exploit the fact, that to find the position of RMQ we only need its mask, but not its first value).
So, we create a table t[sqrt(N)][L][L], and on the precomputing stage for each block we calculate its mask, and see, if t[mask] is already calculated, then skip this block - all information for RMQ in it has already been calculated before.

And here we do an interesting trick: note that each block has length L=logn/2, that means that if we replace each block with its mask (got from +-1 representation) and first value of first element in block (because, +-1-representation is not enough to restore the block), than there could be only 2^L = 2^(logn/2) = sqrt(N) different masks.

Thanks for your reply.

Few questions , if i give you a mask of +-1 , can you tell me where the minimum is ? Why isn't it ambiguous .

if the maks was 1 -1 -1 , the minimum is at position 2, if maks is 1 -1 1, minimum is at position 1 , but if mask is 1 -1 1 -1 ,minimum is at position 1 and 3 . In the original array position 1 and 3 can contain different values ?

So for mask t[100] =2, t[101]=1,t[1010]= ?

How about 1 1 -1 1 -1 -1 ? , 2 1 3 2 1 ? This is where i'm confused.

tryit1 wrote:Thanks for your reply.

Few questions , if i give you a mask of +-1 , can you tell me where the minimum is ? Why isn't it ambiguous .

if the maks was 1 -1 -1 , the minimum is at position 2, if maks is 1 -1 1, minimum is at position 1 , but if mask is 1 -1 1 -1 ,minimum is at position 1 and 3 . In the original array position 1 and 3 can contain different values ?

So for mask t[100] =2, t[101]=1,t[1010]= ?

How about 1 1 -1 1 -1 -1 ? , 2 1 3 2 1 ? This is where i'm confused.

If we have +-1 representation, for example, 1 -1 -1, than it corresponds to a sequence "x x+1 x x-1", there are two minimums (at 0 and 2).
If we have 1 -1 1 -1, than corresponding sequence is "x x+1 x x+1 x", there are three minimums (0, 2, 4), and we can take each of them (they are absolutely equivalent, in terms of LCA problem).

How about 1 1 -1 1 -1 -1 ? , 2 1 3 2 1 ? This is where i'm confused.

This one. We have: "x x+1 x+2 x+1 x+2 x+1 x+1", the only minimum is in 0.