MINXOR - Editorial

[rustinpiece]

PROBLEM LINK:

Practice
Contest

Author: Konstantin Sokol
Tester: Gerald Agapov
Editorialist: Tasnim Imran Sunny

DIFFICULTY:

Medium

PREREQUISITES:

Sqrt decomosition, Trie

PROBLEM:

Given an array A of N integers, you have to process two types of query on the array:

1. L R: find the minimal number in the subarray A[L…R] and count how many times it appears there.
2. L R K: replace each number A_i with the expression (A_i xor K) for the subarray A[L…R].

EXPLANATION:

Sqrt Decomposition and Trie building:

1. Split the numbers in sqrt(N) blocks, where each block contains sqrt(N) numbers. If you are not familiar with sqrt(N) decomposition you may read the section “O(N), sqrt(N) solution” of this tutorial which explains how to answer RMQ with sqrt(N) decomposition.

2. Let every number A_i = a₁a₂… a₁₆ be a 16-bit binary number where a₁ denotes the most significant bit and a₁₆ denotes the least significant bit. The maximum value is less than 65536, so 16 bits are enough to represent the numbers, 2¹⁶ = 65536.

3. Now for each block build a Trie, where all the numbers of that block are inserted into the Trie as a 16-bit binary number. That means, each edge of the trie is either 0 or 1 representing a bit of the numbers.

2nd type of query:

2 L R K

Let pending[j] = The pending value that has to be xor-ed with all the numbers on the j-th block.

Whenever the j-th block is completely inside an update of this type, the new value of pending[j] will be pending[j] xor K .

There could be at most two blocks (the blocks corresponding to left and right endpoint of the query) which are partially covered by the query. For each number A_i inside the query from such blocks just update the new value to be (A_i xor K ). Also delete the old value from the trie of that blocks and insert the new value to the trie.

As there would be at most sqrt(N) blocks and at most 2 * sqrt(N) indexes total on the partially covered blocks and inserting and deleting into the trie takes 16 nodes: the complexity of each type 2 updates would be O(sqrt(N)*16).

1st type of query:

1 L R

Take the minimum of the numbers from each blocks which is completely covered by the query range. All the numbers of j-th block (a block covered completely) has to be xor-ed with pending[j]. For finding the minimum value A_i xor pending[j] (A_i is a number in the trie of that block), the strategy is to try finding each bit of A_i from first bit to last bit. With each k-th bit, check whether the k-th bit can be same as the k-th bit of pending[j], if not then make it different.
After each step, we know one more bit of A_i and that is why Trie can help us in this process. We just need to store the current node of the Trie which corresponds to the current prefix of A_i. From this node we can easily check whether the next bit of A_i can be 0 or 1 and make the decision from that. To get the count of the minimum just store the additional info about the count of how many times a node is visited.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.

[c0d3junki3]

Pretty cool solution

[ashwini007k]

what do you mean by pending value??? any example???

[rustinpiece]

The pending value panding[j] of the j-th block means that all the values inside that block has to be xor-ed with pending[j] .

Initially pending[j]=0 . Assume that for a type 2 update that block is completely covered and say K = 5 for that update. So the new value of pending[j] would be pending[j] = 5
Now say another update which completely covers the j-th block and say K = 7. So the new value of pending[j] would be pending[j] = ( 5 xor 7 ) = 6.

Say A_i is a number from the j-th block, so the actual current value of A_i would be A_i xor pending[j] .