shank_punk's blog

Maximum xor subsequence
By shank_punk, history, 11 years ago, In English

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

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (26)
| Write comment?
»
11 years ago, hide # |
← Rev. 3  
Vote: I like it +13 Vote: I do not like it

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

→ Reply
  • »
    »
    11 years ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it +8 Vote: I do not like it

    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 ?

    → Reply
    • »
      »
      »
      11 years ago, hide # ^ |
       
      Vote: I like it +5 Vote: I do not like it

      Exactly.

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

      → Reply
      • »
        »
        »
        »
        11 years ago, hide # ^ |
        ← Rev. 2  
        Vote: I like it 0 Vote: I do not like it

        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?

        → Reply
      • »
        »
        »
        »
        11 years ago, hide # ^ |
         
        Vote: I like it +1 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          11 years ago, hide # ^ |
           
          Vote: I like it +9 Vote: I do not like it

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

          → Reply
          • »
            »
            »
            »
            »
            »
            11 years ago, hide # ^ |
             
            Vote: I like it -8 Vote: I do not like it

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

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              11 years ago, hide # ^ |
               
              Vote: I like it 0 Vote: I do not like it

              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?

              → Reply
    • »
      »
      »
      11 years ago, hide # ^ |
       
      Vote: I like it +1 Vote: I do not like it

      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.

      → Reply
»
11 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    11 years ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it +8 Vote: I do not like it

    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?

    → Reply
»
10 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply