SUBBXOR - Editorial

editorial
, , ,
1

PROBLEM LINK:

Contest

DIFFICULTY:

MEDIUM

PREREQUISITE:

[Trie][11]
[11]: http://threads-iiith.quora.com/Tutorial-on-Trie-and-example-problems

PROBLEM:

Given an array of positive integers and a number K, find the number of subarrays whose XOR is less than K. XOR of subarray is defined as XOR of all elements in it. Each element is less than 10^6. Number of elements less than 10^5.

EXPLANATION:

Normal O(N^2) solution would time out.
Let f(L,R) = XOR of subarray a[L…R], then f(L,R) = f(1,R) XOR f(1,L-1).
For each index i=1 to N, we can count how many subarrays ending at ith position satisfy the given condition.
Now, suppose, that we have a data structure that allows us to perform this two operations: insert some integer into this structure and for given two integers X and K finds the number of elements already in structure whose XOR with X is less than K.

Then we can solve the task like this:

Answer = 0;
XorOnPrefix = 0;
Structure.insert(0);
for i = 1 to n
    XorOnPrefix = XorOnPrefix xor a_i;
    Structure.insert(XorOnPrefix);
    Answer + = Structure.query(XorOnPrefix,k);
return Answer;

Now, about the data structure. It can be implemented as trie (prefix tree), if we consider integers as binary strings of length logA = 20. Then insertion can be done in O(logA) time. But we also need to keep at each node the number of leaves we will encounter if we go to left side from that node and similarly for right.
How do we do query(x,k)?

 Structure.query(root,x,k,level)
 {
     if level==-1 or root==NULL: return 0
     q=level'th bit of k
     p=level'th bit of x
     if q>0:
         if p==0: // means that all leaves on left of this node will always satisfy 
                 // + queries on right side
               return root.count_left + Structure.query(root.right,x,k,level-1);
         else:  // all leave on right of this node will always satisfy
                // + queries on left of this node
               return root.count_right + Structure.query(root.left,x,k,level-1);
     else:
         if p==0: return Structure.query(root.left,x,k,level-1);
         else: return Structure.query(root.right,x,k,level-1);
 }

SIMILAR PROBLEM:

XORSUM ACM AMRITA’09

1 Like
2

I have two questions -

1.) What does it qualitatively mean to go left or right from a node in the trie? It’s unclear.

2.) Can you please explain atleast with an example how you compute f(L, R) from the trie?
I understand that f(L, R) = f(1, L-1) xor f(1, R), but I don’t see how this fact comes into play when we use the trie. I would be very glad if someone could give just one example.

3

What is level’th in the bit ??

4

@sp1rs, level’th bit means the level’th most significant bit.

  1. Each node in the trie has possibly two nodes (left and right). Going to left means evaluating from that node for the next bit. Try to simulate, you’ll get to know what’s happening.
  2. Example n=3 suppose,

a) we insert 0 in the trie, then we have x=f(1,1) and count how many numbers already present in the trie which when taken xor with x return a number less than K. and then we insert x in the trie.

b) then we insert x=f(1,2) count how many numbers already present in the trie which when taken xor with x return a number less than K. and then we insert x in the trie.

c)       then we insert x=f(1,3) count how many numbers already present in the trie which when taken xor with x return a number less than K. and then we insert x in the trie.

What does the point c) help us?
it tells us how many of subarrays ( [1,3],[2,3] ) satisfy the given condition. Similarily b) tells us how many of subarrays ( [1,2]) satisfy the condition.

1 Like
5

@darkshadows
How the tree is working, do you have any tutorial about the details of the trie used in the problem,
I found one of your link broken.:frowning:

6

http://threads-iiith.quora.com/Tutorial-on-Trie-and-example-problems