XORK Editorial

editorial
, ,
1

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Lavish Gupta
Tester: Abhinav Sharma, Nishank Suresh
Editorialist: Pratiyush Mishra

DIFFICULTY:

2521

PREREQUISITES:

None

PROBLEM:

Given an array A having N elements, a subarray S of A is called good if XOR(S) \geq K, where XOR(S) denotes the bitwise XOR of all the elements of the subarray S.

Find the length of the smallest subarray S which is good. If there is no good subarray, print -1 instead.

EXPLANATION:

XOR Property: If A \oplus B = K, then

K \oplus A = B \\ K \oplus B = A

Let us first solve a subproblem of this where we need to calculate the length of the smallest subarray S such that XOR(S) = K.
For this we first calculate prefix\_xor, where

prefix\_xor[i] = XOR(A_1,A_2....A_i)

Taking initial value of ans as n+1 and a map m
we loop through the array and for a position say i we check as follows:

prefix\_xor[i] = K => ans = min(ans,i) \\ m[prefix\_xor[i] \oplus K] \neq 0= > ans = min(ans,i - m[prefix\_xor[i] \oplus K])

Along with this at each step we also update m as: m[prefix\_xor[i]] = i

Thus at the end of our iterations, if ans = (n+1), then no such subarray exists otherwise the length of the smallest subarray is ans.

Now coming back to the original problem, we can initially get the smallest length of subarray S where XOR(S) = K. Now representing K as:

K = K_{32}K_{31}.......K_1K_0

where K_i represents the i_{th} bit of K.

Looping through the bits of K, we check for the i_{th}, bit, if K_i is 0, then we can take K' as follows:

K' = ((K>>i)|1)<<i

Thus to get K', we set the i_{th} bit of K as 1 and unset all bits of K, post that. Similarly let us define A' as

A'[j] = ((A[i] >> j) << j),\; 1 \leq j \leq N

Thus to get A'[j], we set all the bits, post the i_{th} of A[j] to 0
Now with A' and K', we can again check for smallest subarray S', such that XOR(S') = K'.
By the end of our loop we will get the length of the smallest subarray S, such that XOR(S) \geq K if it exists.

To understand why this work we can see that when we loop from left to right on bits of K, and encounter an unset bit, we change the unset bit of K to set bit, which essentially increases the value of K. The other part is that we unset all the bits post the i_{th} bit , so through this we are actually ignoring these bits and only comparing the bits before and including the i_{th} in our algorithm because if these bits are equal then no matter what the bits are after, the XOR of the subarray would be greater than K.

TIME COMPLEXITY:

O(NlogN), for each test case.

SOLUTION:

Editorialist’s Solution
Setter’s Solution
Tester1’s Solution
Tester2’s Solution

2 Likes
2

I used a binary Trie to solve this problem. Just record in each tree node the max index inside this subtree. Then, loop through XOR(i) and K from highest to lowest bit. If jth bit of K is 1, then we have to go into the subtree which could get 1 at this bit, otherwise break the loop. If jth bit of K is 0, then if there is a subtree which could get 1 at this bit, update the answer and go down to the other subtree. Time complexity is O(NlogK).

3 Likes
3

Yeah even I have a similar implementation. i guess if you search subarray XOR Geeksforgeeks gives you an idea of the logic behind it. It does not solve the exact question of course.

2 Likes
4

Got this right after so many tries.

Used TRIE data structure and handled many edge cases.

solution
Insert:

  1. add the binary representation of the number in the trie
  2. for every node have idx key which stores the maximum index for the prefix pattern. This will be helpful when you are searching for prefix pattern in the TRIE and want to find the maximum index for it.

some more points -
for every node maintain the max index of the bit prefix seen so far. 11010XXX , x could be any bit, many integer can have the same prefix bit pattern, so update the idx to maximum array index.

Search:

  1. keep a running (prefix xor), let say it is called XR;
  2. think of what value you need to xor with XR to make it greater than K. For i’th bit in XR and K, there are 4 possibilities. Just implement those 4 possibilities.
  3. When you get a case where you could pick any ith bit. After picking any ith bit the value become greater than K already, then what bit pattern you after ith does not matter. So it is better you find the bit prefix pattern in the TRIE, but also the bit pattern of the prefix xor whose index in maximum.

[CodeChef: Practical coding for everyone](TRIE Solution )

3 Likes
5

Can someone explain what does this means??

Also why we are unsetting all the post bits and then make it’s prefix_xor, Why not making the prefix_xor by using the same array ??

6

@foxy7 how this is working I m still confused.
For example, lets say k=21
10101 is binary representation of 21
so now acc to the editorial we are only checking for K=22 and 24 → obtained by setting 0 bit and unsetting the post bits.
But now how are u making sure that with k=23 will be covered.