acm icpc amritapuri regional 2009

 XOR SUM

 Given an array of N numbers, we wish to choose a contiguous sub-sequence of the array, so that the bitwise XOR of all chosen numbers is maximum. Bitwise XOR is defined as follows: every bit in the answer is obtained by applying XOR logic on the corresponding bits of the set of numbers. For example 7, 8 and 5 are XORed as follows,

Numbers in binary:  0111  1000  0101  -----  1010

So the answer is 10 (in decimal). The same answer can be obtained in C/C++/Java by using the XOR operator as 7^8^5.

Input 

The first line contains the number of test cases T. The first line of each test-case contains one integer, N (size of the array). The next N lines of each test-case contain integers denoting the elements of the array.


Constraints:

• 1T10
• 1N100, 000
• All input integers will be non-negative and fit into 32 bit signed integer.

Output 

For each test case, output a single line containing the maximum sum that can be obtained.

Sample Input 

2 

5  3  7  7  7  0 

5  3  8  2  6  4

Sample Output 

7 

15

implmentation of tries (source quora by lalit kundu -iiit hyderabad)

I will be writing in this post about Tries and the concept widely used in bit manipulation kind of problems. We'll see 2-3 problems which trie is helpful. First we see what a trie is. Trie can store information about keys/numbers/strings compactly in a tree. Tries consists of nodes, where each node stores a character/bit. We can insert new strings/numbers accordingly.

Source: Wikipedia. 

 But we will be dealing with numbers here, and particularly in binary bits. We'll see as we solve problems.

 Problem1: Given an array of integers, we have to find two elements whose XOR is maximum.

Solution: Suppose we have a data structure in which can satisfy two types of queries: 1. Insert a number X 2. Given a Y, find maximum XOR of Y with all numbers that have been inserted till now. If we have this data structure, we'll insert integers as we go, and with query of 2nd type we'll find the maximum XOR.

So, we trace the path of the number we have to insert, we don't have to draw the existing path again. Insertion of an N length key takes O(N) which is log2(MAX) where MAX is the maximum number to be inserted in trie, because there are at maximum log2(MAX) binary bits in a number. This way we store all the data about all the numbers inserted into trie till now. Now, for query of type 2: Let's say our number Y is b1,b2...bn, where b1,b2.. are binary bits. We start from b1. Now for the XOR to be maximum, we'll try to make most significant bit 1 after taking XOR. So, if b1 is 0, we'll need a 1 and vice versa. In the trie, we go to the required bit side. If favorable option is not there, we'll go other side. 

Doing this all over for i=1 to n, we'll get the maximum XOR possible.

Problem2: Given an array of integers, find the subarray with maximum XOR. 

Solution: Let's say F(L,R) is XOR of subarray from L to R. Here we use the property that F(L,R)=F(1,R) XOR F(1,L-1). How? Let's say our subarray with maximum XOR ended at position i. Now, we need to maximise F(L,i) ie. F(1,i) XOR F(1,L-1) where L<=i. Suppose, we inserted F(1,L-1) in our trie for all L<=i, then it's just problem1. 

ans=0

pre=0

Trie.insert(0)

for i=1 to N:

    pre = pre XOR a[i]

    Trie.insert(pre)

    ans=max(ans, Trie.query(pre))

print ans

SOLUTION

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91

#include<bits/stdc++.h> #include<complex> using namespace std; #define ll long long typedef pair<ll,ll> pp; typedef vector<pair<ll,ll> > vpp; ll min(ll a,ll b) { return(a<b)?a:b; } ll max(ll a,ll b) { return(a>b)?a:b; } typedef struct $ { struct $ *left; struct $ *right; }ss; void insert(ss *head,ll a,ll count) { if(count ==-1)return; if((a>>count)&1) { if(head->right==NULL) { head->right=(ss *)malloc(sizeof(ss)); head->right->right=NULL; head->right->left=NULL; } insert(head->right,a,count-1); } else { if(head->left==NULL) { head->left=(ss *)malloc(sizeof(ss)); head->left->right=NULL; head->left->left=NULL; } insert(head->left,a,count-1); } } void recieve(ss *head,ll a,ll count,ll &num) { if(count==-1)return; if((a>>count)&1) { if(head->left!=NULL) recieve(head->left,a,--count,num); else { num+=(ll)pow(2,count); recieve(head->right,a,--count,num); } } else { if(head->right!=NULL) { num+=(ll)pow(2,count); recieve(head->right,a,--count,num); } else recieve(head->left,a,--count,num); } } int main() { ll t,n,num,a[400005],prefix[400005]={0},ma=0; scanf("%lld",&t); while(t--) { ma=0; scanf("%lld",&n); for(ll i=0;i<n;i++) scanf("%lld",a+i); ss *x=(ss *)malloc(sizeof(ss)); insert(x,0,31); for(ll i=1;i<=n;i++) { prefix[i]=prefix[i-1]^a[i-1]; insert(x,prefix[i],31); num=0; recieve(x,prefix[i],31,num); ma=max(ma,num^prefix[i]); } printf("%lld\n",ma ); } return 0; }