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 ).
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3611 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | Radewoosh | 3415 |
| 8 | Um_nik | 3376 |
| 9 | maroonrk | 3361 |
| 10 | XVIII | 3345 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 162 |
| 2 | adamant | 148 |
| 3 | Um_nik | 146 |
| 4 | Dominater069 | 143 |
| 5 | errorgorn | 141 |
| 6 | cry | 138 |
| 7 | Proof_by_QED | 136 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 10 | soullless | 133 |
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, reduced row 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 not 0:
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
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?
Click HERE . Your problem is discussed in Problem 2 section :)