Algorithm

USACO Section6.1 Cow XOR (cowxor)

Problem Summary

Given a sequence of integers, d[1],d[2],…,d[N] (1<=N<=100,000), find the consecutive subsequnce such that the bitwise XOR between the subsequence has the maximum value. (0<=d[i]<(2^21))

Solution

At first, we need to know a property of xor (exclusive or) operation:

If a xor b equals c, then the xor of any two of a,b,c, equals the other one.

Let xr[i] be the xor of d[1],d[2],…,d[i], 1<=i<=N. Suppose xr[0]=0, then the xor of the sequence d[i],…,d[j] equals xr[i-1] xor xr[j].
Apparently, the maximam value is max{xr[i] xor xr[j]}, where 0<=i<j<=N.

For each j, 1<=j<=N, we only need to find an i (0<=i<j), such that xr[i] xor xr[j] is maximal. That is, we need to find a xr[i] which is most different from x[j]. Since N can be as large as 100,000, we need to use an algorithm faster than O(N^2).

Note that d[i] is in the range from 0 to (2^21)-1, so xr[i] is also in this range, and its binary representation has at most 21 digits.

Limited length and limited options for each digit lead me to think about Trie, which can greatly reduce time complexity. So I used Trie to keep values of the array xr.

Code

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
92
93
94
95
96
97
98
99
100
nclude <iostream>
#include <fstream>
using namespace std;
const int max_len = 21;
const int maxn = 100002;
int n,d[maxn];
int ans,st,en;
struct Node
{
public:
	int rank;
	Node *l,*r;
	Node() { rank=0; l=r=NULL; }
	void add(int cur,int r);
} trie;
void Node::add(int cur,int r)
{
	int idx = max_len,tmp;
	Node *p = &trie;
	while(idx>=0 && p!=NULL)
	{
		tmp=cur&(1<<idx);
		if(tmp==0)
		{
			if(p->l==NULL)
				p->l=new Node();
			p=p->l;
		}
		else
		{
			if(p->r==NULL)
				p->r=new Node();
			p=p->r;
		}
		idx--;
	}
	p->rank=r;
}
void find_best(int cur,int cur_end)
{
	int idx = max_len,tmp;
	Node *p = &trie, *q;
	while(idx>=0 && p!=NULL)
	{
		int tmp=cur&(1<<idx);
		if(tmp==0)
		{
			if(p->r!=NULL) q=p->r;
			else q=p->l;
		}
		else
		{
			if(p->l!=NULL) q=p->l;
			else q=p->r;
		}
		p=q;
		idx--;
	}
	tmp = (d[p->rank]) ^ cur;
	if(tmp>ans)
	{
		ans=tmp;
		st=p->rank+1;
		en=cur_end;
	}
}
int main()
{
	fstream fin("cowxor.in",ios::in);
	fstream fout("cowxor.out",ios::out);
	trie.add(0,0);
	ans=-1;
	fin>>n;
	for(int i=1;i<=n;i++)
	{
		fin>>d[i];
		d[i]^=d[i-1];
		find_best(d[i],i);
		trie.add(d[i],i);
	}
	fout<<ans<<" "<<st<<" "<<en<<endl;
	fin.close();
	fout.close();
	return 0;
}