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 inblock 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)
RMQ problem
Moderator: Board moderators

 Learning poster
 Posts: 51
 Joined: Tue Sep 04, 2007 2:12 pm
 Location: Russia, Saratov
 Contact:
Re: RMQ problem
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[i1]+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, +1representation 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.
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[i1]+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, +1representation 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.
Re: RMQ problem
Thanks for your reply.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, +1representation is not enough to restore the block), than there could be only 2^L = 2^(logn/2) = sqrt(N) different masks.
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.

 Learning poster
 Posts: 51
 Joined: Tue Sep 04, 2007 2:12 pm
 Location: Russia, Saratov
 Contact:
Re: RMQ problem
If we have +1 representation, for example, 1 1 1, than it corresponds to a sequence "x x+1 x x1", there are two minimums (at 0 and 2).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 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).
This one. We have: "x x+1 x+2 x+1 x+2 x+1 x+1", the only minimum is in 0.How about 1 1 1 1 1 1 ? , 2 1 3 2 1 ? This is where i'm confused.