hello_its_me's blog

Help with maximum xor subarray
By hello_its_me, 12 months ago, In English

I was trying to solve this problem from cses that is the maximum xor of a subarray of a given array. Can someone please help me to solve it. I tried for sometime but could not find any way.

This is the problem : Max Xor Subarray

Also it will be very helpful if you could give hints on solving the maximum Xor of subset of an array which i think is somewhat similar to the first problem. This one : Max Xor Subset

Thanks in advance.

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
12 months ago, hide # |
 
Vote: I like it +16 Vote: I do not like it

First one using binary trie.

Second one using xor basis.

→ Reply
»
12 months ago, hide # |
 
Vote: I like it +29 Vote: I do not like it

The maximum XOR subarray can be converted into the XOR of the maximum two XOR prefix sums, which can then be easily solved using 01-trie.

The maximum XOR subsets can be queried directly by inserting them into a linear basis.

→ Reply
»
12 months ago, hide # |
 
Vote: I like it +4 Vote: I do not like it

The two comments above me are literally giving the same, correct answer. Yet there's somehow a huge disparity in upvotes / downvotes. Make it make sense pls

→ Reply
»
12 months ago, hide # |
 
Vote: I like it -11 Vote: I do not like it

I think that you can use a slightly modified Kadane's algorithm. Instead of summing the values in the array, you just xor them.

code
→ Reply