XRQRS - Editorial

[darkshadows]

PROBLEM LINK:

Practice
Contest

Author: Fedor Korobeinikov
Tester: Shiplu Hawlader
Editorialist: Lalit Kundu

DIFFICULTY:

MEDIUM-HARD

PRE-REQUISITES:

Tutorial on trie and example problems

PROBLEM:

Given an initially empty integer array (1-indexed) and M queries:

• Type 0: Add the integer number x at the end of the array.
• Type 1: On the interval L..R find a number y, to maximize (x xor y).
• Type 2: Delete last k numbers in the array
• Type 3: On the interval L..R, count the number of integers less than or equal to x.
• Type 4: On the interval L..R, find the k_th smallest integer (k_th order statistic).

1 ≤ M ≤ 5 * 10⁵

QUICK EXPLANATION:

Make a trie of integers experessed in binary and at each node in trie, also store the indexes of numbers which pass through that node.

EXPLANATION:

If you don’t know about tries, read the complete post given in pre-requisites and try to implement those problems.
Let’s say in query of Type 1, L=1 and R=N, how will we solve?
We’ll build a trie and we can insert in O(number of bits) each element. We can also delete in O(number of bits) any number, but we’ll have to store at each node count of elements passing through that node. The following image doesn’t store counts at node.

For maximum xor query, for L=1 and R=N, we’ll just traverse over the whole trie and starting from most significant bit(MSB), we try to form largest number possible. Example:

But our query is for range L to R, so we store at each node also the indexes of numbers which pass through the that node. For example:

But how does this help?
When we go down the tree during a query and maximising the xor, we go in a direction that contains at least one index in range L to R, otherwise we go in the other direction. Let’s consider the above image as example and we want maximum xor with ‘110’ in range [1,2] (note the zero indexing):

About inserting a number x which occurs at position y in array, we express x in binary and then traverse the trie and at each step push the value y at each vector of node that we pass through.
So, a total of log(x) times, we’ll push y in different vectors. Therefore, total memory used won’t exceed M*log(MAX). These vectors will always be sorted as we insert in increasing order of y.

About deleting last k elements, we can do it in O(h * k)(h=height of trie = log MAX). Point worth noting is that sum of k over all deletion queries can’t exceed M. So, we can do deletions in O(h * k). While deleting one element from end, we just go traverse over the trie along the path of element being deleted and pop from the end of the vector(ie. pop the index of element) at each node.

Now, about the type4 query, we need k’th smallest element in range L to R.
Again, let’s solve for L=1, R=N.
I start from the root, and at each step I know, that if I go towards left, I’ll encounter say K1 leaves(numbers) and at right side I’ll encounter K2 leaves(numbers) and considering that all numbers on left side are smaller than those at right side, I can easily make a decision whether I want to go to left side or right side(ie. whether this bit of my answer will be set or not, we already have calculate previous bits of our answer).

Similarily to the way we handle xor range queries, we can do for a range query in k’th order statistics. We can count number of indexes in range [L,R] in a vector using lower_bound, upper_bound.

SOLUTIONS:

Setter’s solution
Tester’s solution

[neo1tech9_7]

This problem can also be done using persistent trie and persistent segment trie. I know it’s an overkill but if you want to practice persistent data structures it’s really great

My solution : http://www.codechef.com/viewplaintext/5703145

[sarasgupta]

I did it using persistent segment tree.

XRQRS - Codechef

Pre-requisites - Segment tree with lazy propagation

This problem gives 5 type of queries.
0. Add an element to the end of the list
Find a number y from L…R such that x^y is maximised
Delete the last k elements from the list
Find how many numbers from L…R are smaller than x
Find the kth element in range L…R

1<=x<=500000

First we try and make an algorithm which answers Q0 and Q3

• What if we make segment trees for each subarray L…R
  Each segment tree would be of size 500005
  For each element A[i] in the subarray we can increment the range A[i]…500004 in the segment tree containing A[i] using lazy propagation
  Time and Space Complexity=O(n^3log(n))

• What if we make segment trees for all subarrays of the from 1…R
  Calculate the ans(L, R, x) using ans(1, R, x) - ans(1, L-1, x)
  ans(L, R, x) = number of nos greater than or equal to x from L…R
  Time and Space Complexity=O(n^2log(n))

• We can use a special data structure called persistent segment tree. Using this data structure we can all store and compute subarrays of the form 1…R using only Nlog(N) space and time.
  We can see that segment tree for 1…N is quiet similar to segment tree of 1…N-1. We can use this fact to reduce time and space complexity.
  Whenever an element is added we make a new root for it and make new nodes for the tree if they are updated or point to the previous ones if there is no change.
  With an example I have shown how the segment tree is constructed when 3 and 2 are added to an empty array given that the maximum value that can be pushed is 7.

For Q4 we have to maintain mx in every node referring to the number of elements less than or equal to r (which is the max limit of that node).
Using this we can find out if the number we’re looking for is in the left subtree or the right subtree.
For example if we want to find the kth number in the subarray, than if we know that the number of numbers in the right half is (say 0-3) is less than k than the number must be in the right half (say 4-7).

For Q1 we compare a simpler case of finding a number y in an already sorted array.
We start from the MSB(most significant bit) to the LSB of x and check if it is set.
If it is set than we than we find a number smaller than (2^MSB). If such a group of numbers exist than we find the number in this group else we search for the number in the other group and move on to the next bit.
If it is not set than we find if a number exists which is greater than or equal to (2^MSB). If such a group of numbers exists than we go on searching for the number in this group else we search for the number in the other group and move on to the next bit.
To implement this algorithm in the persistent segment tree we can increase the range of values which can be input from 0-500004 to 0-524288(=2^19-1). This helps us a lot. We can move in one direction or the other according to the bits set in x and also checking if a any number exists with the given requirement in that subtree using mx.

example
link text

my code
link text

[witalij_hq]

Hey, I also did it using persistent Trie. This solution is better in time - it saves log(n) in all operations.

In your case each query requires log(MAX) * log(n) operations. log(MAX) for searching in trie, and log(n) for queries in each node.

Using persistent trie you can avoid storing numbers that pass through each node. (please see the solution of neo1tech9_7).

BTW, my solution with persistent trie uses about 0.81 sec in c++ and gets TLE in java, so I can’t understand how your solution, which is slower, could pass…

[shubham011]

don’t know why we have 5 sec for SEALCM and 1.5 sec for this question…
and java always show TLE for segment tree problems…

all we need to do is to learn c++ ?

[fauzdar65]

i did that… it think it’s simpler as we don’t have to store any list on each node of the trie as in the above solution…just the last inserted index is enough,and also we get O(1) deletion…

[dragonslayerx]

why the timelimits were set so strict . implemented the same idea in c++ as in the editorial with every possible minute optimizations… still got TLE for 2 testfiles everytime. But definitely learnt a lot…nice question i must say… eagerly waiting for a writeup about the solution with persistent tries

[vishfrnds]

Solved with “persistent augmented tries” only

1 insertion - O(number of bits)

2 MAX XOR - O(number of bits)

3 Rank - O(number of bits)

4 kth number - O(number of bits)

5 deletion - O(1)

number of bits = 20

max space - N log(N)

http://www.codechef.com/viewsolution/5792195

[anuj95]

This question made me learn a lot . I wish there are more questions like XRQRS and SEALCM inplace of the first 6 questions that were there in this contest in the next long contest .

[adi1994]

Really an awesome question…Learnt a lot…In fact tried different data structures for the problem…
But even after implementing the solution as mentioned in the editorial, still getting TLE for one last test case. Can’t think of any further optimizations.

The link to the solution : http://www.codechef.com/viewsolution/5882154

[piotrekg2]

I’ve managed to solve testcases where M <= 5 * 10^4. I used a combination of segment tree and trie.
Each segment tree element has a trie which contains all elements in that segment. This gave me a solution with time complexity O(logn * #bits) for all queries but k’th element. For k’th element I’ve used a binary search in combination with query of type 3 (#elements <= x).

I’ve also compressed trie’s edges so that it looked more like suffix tree. It performed about ~2 times faster than uncompressed version. solution

[pavel]

When getting TLE for the last test case, check your implementation of the XOR query. For the XOR query, you don’t need to count the number of indices between L and R in each node. You only need to know, whether there is at least one. As a result, you don’t need to calculate both lower_bound and upper_bound - only one of them is sufficient (find it and check, whether the value is between L and R). This way, you can reduce number of steps in each node from 2*log(N) to 1*log(N).

[xellos0]

There’s a fairly simple (but apparently too slow) solution in O(log M log x) per query.

Just make a segment tree / RMQ-like structure of binary tries (which are, in this case, compressed segment trees). Each interval can be split into around log(M) intervals of lengths equal to powers of 2; each trie includes all numbers in one such interval; also, each index is covered by log(M) of them.

Queries 0 and 2 are adding/removing from these log(M) tries.

Query 3 is just getting the sum of an interval in each trie, just like in a standard segtree.

Query 1 for each trie is moving down that trie; if the vertex that corresponds to taking the next bit opposite to that of x exists, move to it; otherwise, move to the other vertex (it has to exist, because these tries have leaves in depth exactly log(x)).

Query 4 needs moving down tries in parallel - find out how many numbers (in all tries) have 0 as the next bit; if it’s less than k, subtract that number from k and take 1 as the next bit of the answer; otherwise, take 0.

I tried implementing this and speeding it up, but only got to around <= 2s. I don’t think I had a chance with this time limit…

[codeshaker]

code shows Access Denied!!

[brobear1995]

Is there any standard template for trie?

[triploblastic]

i used persistent Trie for this problem. but it still fails the last test case . code complexity is M2lgn a t most if only type 3 query ar considered.
http://www.codechef.com/viewsolution/5888271
here is my last submission where code complexity is M*lgn for every query. but still getting tle :’(
http://www.codechef.com/viewsolution/5888456

[adi1994]

Thanks…Got ACed…In fact, time reduced considerably.

[ak29]

i cant figure out how to do type 3 query using the method mentioned in editorial…can anyone help?

[trophies]

Probably, this problem is best done with persistence.

[ankursmooth]

access denied for all solution files in Jan 2015 editorials… “This XML file does not appear to have any style information associated with it. The document tree is shown below.
…”