### shank_punk's blog

By shank_punk, history, 7 years ago,

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 ).

• 0

 » 7 years ago, # | ← Rev. 3 →   +13 A hint:xor of two numbersx_1 xor x_2 xor x_3 xor ... xor x_(i-1)andx_1 xor x_2 xor x_3 xor ... xor x_j givesx_i xor x_(i+1) xor ... xor x_(j-1) xor x_j
•  » » 7 years ago, # ^ | ← Rev. 2 →   +8 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 ?
•  » » » 7 years ago, # ^ |   +5 Exactly.In addition, you should add 0 to trie. To include xor starting from x_1 (1-based)
•  » » » » 7 years ago, # ^ | ← Rev. 2 →   0 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?
•  » » » » » 7 years ago, # ^ | ← Rev. 2 →   +5 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.
•  » » » » » » 7 years ago, # ^ | ← Rev. 4 →   +1 edit : I realized my approach will give wrong answer.
•  » » » » » » » 7 years ago, # ^ |   0 It is gauss elimination I guess
•  » » » » » » » » 7 years ago, # ^ | ← Rev. 2 →   0 Guesing doesn't work in competitive programming :) . You need to be as sure as you can.
•  » » » » » » » » » 7 years ago, # ^ |   0 I am sure it's Gaussian elimination.
•  » » » » » » » » » 7 years ago, # ^ |   0 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?
•  » » » » » » » » » 7 years ago, # ^ |   0 Row echelon form won't help. You need, as has been said, reduced row echelon form, and each row must have MSB as a leading coefficient.It gives maximal XOR sum because of this: Reduced form is equivalent to original set of numbers. Removing any non-zero row from the resulting sum will make it lower.
•  » » » » » » » » » 7 years ago, # ^ |   0 Thanks! Got it. :)
•  » » » » » 7 years ago, # ^ | ← Rev. 6 →   +6 I will re-write it as C++ version, I confused this with another code.
•  » » » » » » 7 years ago, # ^ |   0 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.
•  » » » » » » » 7 years ago, # ^ | ← Rev. 2 →   +1 I am really sorry, I was little bit confused. I editted two part if A[i] and (1<
•  » » » » » » » 7 years ago, # ^ | ← Rev. 2 →   +1 I am really sorry for confusing you.I just implemented row echelon form and got accepted in SPOJ.Code
•  » » » » » » » » 6 years ago, # ^ |   0 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.
•  » » » » 7 years ago, # ^ |   +1 I understand the bit about (x1 ^ ......xi) ^ (x1 ^ ......xj) = (xi ^ .....xj), but I do not understand the part about using a tree. Help?
•  » » » » » 7 years ago, # ^ |   +9 Don't worry, you will be able to read about it in the editorial after the contest finishes.
•  » » » » » » 7 years ago, # ^ |   -8 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."
•  » » » » » » » 7 years ago, # ^ |   0 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?
•  » » » 7 years ago, # ^ |   +1 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.
•  » » » » 7 years ago, # ^ |   0
•  » » » » » 7 years ago, # ^ |   0 oh....thanks :)
 » 7 years ago, # |   0 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.
•  » » 7 years ago, # ^ | ← Rev. 2 →   +8 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?
•  » » » 7 years ago, # ^ |   0 Yes I do think it is proper trie question.I too am doing trie these days and solved similar question with somewhat low constraint
 » 6 years ago, # |   0 Click HERE . Your problem is discussed in Problem 2 section :)