shank_punk's blog

Maximum xor subsequence
By shank_punk, history, 9 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?
»
9 years ago, # |
← 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
  • »
    »
    9 years ago, # ^ |
    ← 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
    • »
      »
      »
      9 years ago, # ^ |
        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
      • »
        »
        »
        »
        9 years ago, # ^ |
        ← 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
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
          ← Rev. 2   Vote: I like it +5 Vote: I do not like it

          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
            ← Rev. 4   Vote: I like it +1 Vote: I do not like it

            edit : I realized my approach will give wrong answer.

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

              It is gauss elimination I guess

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

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

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

                  I am sure it's Gaussian elimination.

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

                  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?

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

                  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:

                  1. Reduced form is equivalent to original set of numbers.
                  2. Removing any non-zero row from the resulting sum will make it lower.
                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  9 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Thanks! Got it. :)

                  → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
          ← Rev. 6   Vote: I like it +6 Vote: I do not like it

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

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

            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.

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

              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/

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

              I am really sorry for confusing you.

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

              Code

              → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          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
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            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
          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
              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
            • »
              »
              »
              »
              »
              »
              »
              9 years ago, # ^ |
                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
    • »
      »
      »
      9 years ago, # ^ |
        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
»
9 years ago, # |
  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
  • »
    »
    9 years ago, # ^ |
    ← 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
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply