QN01 - XOR Game
You are given an array of n integers ( 0 <= n <= 1000 ). Find a contiguous subsequence of these numbers [ ai, aj ] ( 1 <= i, j <= n ), such that the Exclusive-OR of these numbers is maximum. ( That is, ai XOR ai+1 XOR... aj should be maximum ).
The test case contains exactly 2 lines of input.
The first line contains a single integer n ( 0 <= n <= 1000 ), the total number of integers in the sequence given to you.
The next line contains n space separated integers such that the ith integer denotes ai. ( 0 <= ai <= 109 ). Note that these integers need not necessarily be distinct.
Output two lines. In the first line, print out the value of the maximum XOR.
In the second line, print out i and j with a space separating them, such that [ ai, aj ] ( both endpoints inclusive ) denotes the contiguous subsequence with the maximum XOR value.
In case there is more than one subsequence with the maximum XOR value, print out the pair ( i, j ) such that ( i, j ) is lexicographically smallest. ( Formally, we say that a pair ( a, b ) is lexicographically smaller than another pair ( c,d ) if and only if (i) a < c or (ii) a=c and b < d. )
NOTE : The subsequence must be non-empty, but may be allowed to contain just one integer. ( i.e, in this case, i = j )
1 2 3
- In the first test case, since there is only one number, the maximum XOR would be simply the value of that number ( in this case, 4 ), and i = j = 1.
- In the second test case, the maximum XOR value is 3, but there are 2 contiguous subsequences that define the same XOR value - (i) [ 1, 2 ] since 1 XOR 2 = 3 (ii) [ 3, 3 ] since this subsequence contains just the single integer 3. But since [ 1, 2 ] is lexicographically smaller than [ 3, 3 ], [ 1, 2 ] is the desired output.
SAME PROBLEM WITH BETTER CONSTRAINTS : https://icpcarchive.ecs.baylor.edu/index.php?Itemid=8&category=345&option=com_onlinejudge&page=show_problem&problem=2683
AC in one go. Didn't expect that.Last edit: 2017-01-25 12:21:58
O(n^2) passes.... that too with 0.0 s
lol . O(n^2) passes !
Just trie !! ;) 0.0secLast edit: 2016-07-05 18:30:24
better use "trie" than the brute force approach....
poor test cases !!! wondering how O(n^2) got accepted
what is O(nlogn) algorithm.......?
...Why would I use long long