Friday, February 12, 2016

SUBXOR SPOJ (Trie) Solution - C++

Algorithm:

1. If you want to get XOR of array elements in range [I, J], you can do it by taking the XOR of [1, I-1] with XOR[1, J]. (How does this solve the problem? - See next points.)
2. Make a trie of the bit representation of the XOR of elements.

Suppose the array is: 4, 1, 3, 2, 7. and k = 2.

      Binary Rep.     XOR    K=2 Bin = 010

4    100                  100
1    001                  101
3    011                  110
2    010                  100  <-- (example case below)
7    111                  011

For each element of the array,

1. Insert the value 0 to the Trie (test for cases like when there is only one element present and is less than k).
2. Find it's XOR with the previous value (0 if first). Now find how many subarrays are present whose XOR is less than k. How? ->

Consider the case when you've inserted XOR with element 3 and considering the element 2 to pass its XOR to query.
Now k = 2 its binary rep. is 010. Now you take this representation of k and the current XOR value's (for 2 = 100) binary representation to guide your search through the trie.

k1 = 0. Now above the value 2 in the array, all those XORs whose bit at index = 1 is = 1, when taken XOR with "1"00 will give a value 0. These XORs are the ones who may be less than or equal to the value k. Those XOR values who have a 0 in the first bit when taken XOR with "1"00 will give 1 which means that all those XORs are greater than k. Here's the full detail-

Check the first bits below:-

100 ^ 100 -> 000 = (0 in the first position). Can be less than k. This represents the XOR of 1,3,2 as you are taking xor of 4,1,3,2 with 4 so you get xor of 1,3,2.

100 ^ 101 -> 001 = (0 in the first position again). Can be less than k. This represents the XOR of 4,1 with XOR of 4,1,3,2 = XOR of 3, 2.

100 ^ 110 -> 010 = (0 in the first position again). Can be less than k. This represents the XOR of 4,1,3 with XOR of 4,1,3,2 = XOR of 2.

100 ^ 000 (the first 0 we inserted in the trie) -> represents the XOR of 4,1,3,2.

So all the possible sequences ending at 2 have been considered. A trie thus helps to get the answer fast.

3. Do this until the last element of the array has been considered.

Code (C++):

#include <stdio.h>

#define MAX 200000

struct node{
 int nL, nR;
 int leftIndex, rightIndex;

 node(){
  nL = 0;
  nR = 0;
  leftIndex=-1;
  rightIndex=-1;
 }
};
  
int gIndex=0;

void insert(int value, int index, int depth, node *tree){
 for(int i = depth-1;i>=0;--i){
  int bit = value>>i & 1;
  if(bit){
   tree[index].nR++; 
   if(tree[index].rightIndex==-1){ 
    tree[index].rightIndex = ++gIndex;
    index = gIndex;
   }else index = tree[index].rightIndex;
  }else{ 
   tree[index].nL++;
   if(tree[index].leftIndex==-1){
    tree[index].leftIndex = ++gIndex;
    index = gIndex;
   }else index = tree[index].leftIndex; 
  }
 } 
}

int query(int value, int compare, int index, int depth, node* tree){
 int ans=0;
 for(int i=depth-1;i>=0;--i){
  int vBit = value>>i & 1;
  int cBit = compare>>i & 1;
  if(cBit){ 
   if(vBit){ans += tree[index].nR; index = tree[index].leftIndex;}
   else{ans += tree[index].nL; index = tree[index].rightIndex;} 
  }else{ 
   if(vBit) index = tree[index].rightIndex;
   else  index = tree[index].leftIndex;
  }
  if(index==-1)break; 
 }
 return ans;
}

int main(){
 int d;
 scanf("%d", &d);
 while(d--){ 
  node tree[MAX];
  gIndex=0;
  int n, k;
  scanf(" %d %d", &n, &k);
  int XOR = 0, t=0;
  long long ans=0;
  insert(0, 0, 20, tree);
  while(n--){
   scanf(" %d", &t);
   XOR = XOR ^ t;
   ans += query(XOR, k, 0, 20, tree);  
   insert(XOR, 0, 20, tree);
  }
  printf("%lld\n", ans);
 }
}

1 comment:

  1. Why is 20 being chosen as the depth always?

    ReplyDelete