Here you will find solutions of many problems on spoj. If you want solution of some problem which is not listed in blog or have doubt regarding any spoj problem (which i have solved) or any programming concept (data structure) you can mail me @ raj.nishant360@gmail.com
And my humble request to you all that don't copy the code only try to understand the logic and algorithm behind the code. I have started this because if you tried as hard as you can and still can't find any solution to the problem then you can refer to this.
You can read my answer how to start competitive programming CLICK HERE

Saturday, May 24, 2014

SUBXOR-SubXor

SubXor

Given below c code for subxor spoj
Here I am posting iterative and recursive method to implement Tries.But if you want to understand the problem then follow recursive method.

Here question is based on concept of xor and I have implemented it through Trie .

Basic idea is :-
xor(i,j) means XOR of elements from indexed i to j of an Array

XOR(i,j) = XOR(1,i-1)^XOR(1,j);

This can be proved as 

A^A = 0     & A^0 = A;
Hence if we XOR the total XOR from 1 to j with total XOR from 1 to i-1 ,it will nullify the effect  of XOR(1,i-1) in XOR(1,j) and the remaining XOR will be XOR(i,j);

If you want to study about Tries then CLICK HERE

If you still have problem you can ask me @ raj.nishant360@gmail.com

Iterative Method to implement add and query function
#include <bits/stdc++.h>
using namespace std;
class Node
{
public:
    int lCount,rCount;
    Node *lChild,*rChild;
    Node()
    {
        lCount=rCount=0;
        lChild=rChild=NULL;
    }
};
void addBit(Node *root,int n)
{
    for(int i=20;i>=0;i--)
    {
        int x= (n>>i) & 1;
    
        if(x)
        {
            root->rCount++;
            if(root->rChild == NULL)
                root->rChild = new Node();
            root = root->rChild;
        }
        else
        {
            root->lCount++;
            if(root->lChild == NULL)
                root->lChild = new Node();
            root = root->lChild;
        }
    }
}
int query(Node *root,int n,int k)
{
    if(root == NULL)
        return 0;
    int res = 0;
    for(int i=20;i>=0;i--)
    {
        bool ch1=(k>>i) & 1;
        bool ch2=(n>>i) & 1;
        if(ch1)
        {
            if(ch2){
                res+=root->rCount;
                if(root->lChild == NULL)
                    return res;
                root = root->lChild;
            }

            else{
                res+=root->lCount;
                if(root->rChild == NULL)
                    return res;
                root = root->rChild;
            }
        }
        else
        {
            if(ch2){
                if(root->rChild == NULL)
                    return res;
                root= root->rChild;
            }
            else{
                if(root->lChild == NULL)
                    return res;
                root= root->lChild;
            }
        }
    }
    return res;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,k;
        scanf("%d%d",&n,&k);
        int temp,temp1,temp2=0;
        Node *root = new Node();
        addBit(root,0);
        long long total =0;
        for(int i=0;i<n;i++)
        {
            scanf("%d",&temp);
            temp1= temp2^temp;
            total+=(long long)query(root,temp1,k);
            addBit(root , temp1);
            temp2 = temp1;
        }
        printf("%lld\n",total);
    }
    return 0;
}