XRQRS - Editorial

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 kth smallest integer (kth order statistic).

1 ā‰¤ M ā‰¤ 5 * 105

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:

image

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

11 Likes

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 :smiley:

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

3 Likes

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

7 Likes

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ā€¦

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++ ?

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ā€¦

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

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

2 Likes

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 .

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

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

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).

1 Like

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ā€¦

code shows Access Denied!!

1 Like

Is there any standard template for trie?

i used persistent Trie for this problem. but it still fails the last test case :frowning: . 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

Thanksā€¦Got ACedā€¦In fact, time reduced considerably. :smiley:

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

Probably, this problem is best done with persistence.

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.
ā€¦ā€