Hi guys. I was trying to solve this problem but couldn't arrive with a working solution . We have to find the maximum xor contiguous sub-sequence . I have no idea how to start (I know we have to use trie , but don't know how to can find the max xor contiguous sub-sequence ).

A hint:

xor of two numbers

x_1 xor x_2 xor x_3 xor ... xor x_(i-1)

and

x_1 xor x_2 xor x_3 xor ... xor x_j gives

x_i xor x_(i+1) xor ... xor x_(j-1) xor x_j

Thanks you very much . I think got it .

for i from(1 to n-1) input[i] ^= input[i-1]

Build a trie with input and find max xor pair ?

Exactly.

In addition, you should add 0 to trie. To include xor starting from x_1 (1-based)

What if the question was to find maximum xor sub-sequence (not necessarily contiguous). The best I can think is

O(n*max(A[i])). Is their some solution better than this?You can do with O (n * lg(Range of number) )

You can make n * (number of bits) matrix, every row is binary representation of numbers, and make reduced row echelon form, and xor every nonzero entry of column.

edit : I realized my approach will give wrong answer.

It is gauss elimination I guess

Guesing doesn't work in competitive programming :) . You need to be as sure as you can.

I am sure it's Gaussian elimination.

Gaussian elimination leads to row echelon form, and I already know that. But I don't know how that works in this situation. In gaussian elim. you operate n-k rows against kth row. How does that give maximum xor sum?

Row echelon form won't help. You need, as has been said,

reducedrow echelon form, and each row must have MSB as a leading coefficient.It gives maximal XOR sum because of this:

Thanks! Got it. :)

I will re-write it as C++ version, I confused this with another code.

Thanks.

"for k = 0 to N-1: A[k] <- r"

Shouldn't this be A[k] <- A[k] ^ r ?

Also I am still unable to completely get whats happening in this pseudocode. What i get it that for each bit you are trying to find the first A[i] such that bit j of A[i] = 0 and some magic afterwards.

I am really sorry, I was little bit confused. I editted two part

if A[i] and (1<<j)

is not0:for k = 0 to N-1: if A[k] and (1<<j) is not 0 : A[k] <- A[k] ^ r

I will just code with C++ and post code.

PS 1. I found the problem http://www.spoj.com/problems/XMAX/

I am really sorry for confusing you.

I just implemented row echelon form and got accepted in SPOJ.

Code

Like if have a similar problems as you need to find "xored" prefix[1-r] and "xored" suffix[l-n] r < l so that xor of prefix and suffix maximum I have solution of O(n log n), can it be improved using your approach.

I understand the bit about (x1 ^ ......xi) ^ (x1 ^ ......xj) = (xi ^ .....xj), but I do not understand the part about using a tree. Help?

Don't worry, you will be able to read about it in the editorial after the contest finishes.

I'm not planning on placing in the cash by a long shot. Actually just trying to learn. It is a fun hobby for me, and I've been thinking about this problem for better part of a day.

FYI, from the 'contest' description:

"it is not alright to copy other people's solutions or seek other people's help to solve a problem

without understanding it. The dividing line may seem to be thin but it can be captured by the spirit of learning.If whatever you are doing is making you learn while you do so, we tend to believe that it is alright."On the other side,

Discussing CodeChef's problems or any aspect of problem, on any other platform on web, on identification, could lead to disabling of respective account and banning from the community.And if the part you copied have some actual weight — well, in this case I think that it is very stupid. I'll ask some of problem-setters to share solutions to all 9 classic problems and a few best solutions to challenge problem — for sure I'll spend time to understand them, and I'll definitely learn a lot, so it should be fine, right?

I didn't understand how we can find max xor pair from trie tree? May be I did understand the structure of trie tree for input array.

Trie : max xor pair

oh....thanks :)

I think the approach should be a modified Kadane's Algorithm, in which instead of the maximum sum contiguous subsequence, we just have to find the maximum XOR continuous subsequence.

Shouldn't be too difficult to implement.

I don't think it will work. In kadane's algorithm, we update Max ending to zero, only if Max ending is negative. We can't do the same for this(we don't get any negative values XORing two numbers).

Lets have a case : {7 6 1 2 4 8 , 1 1 12 15 8} how will you use kadane's algo and get 15 as the max XOR cont. subsequence?

Yes I do think it is proper trie question.I too am doing trie these days and solved similar question with somewhat low constraint

Click HERE . Your problem is discussed in Problem 2 section :)