skavurskaa's blog

Subset xor problem (need help)
By skavurskaa, history, 9 years ago, In English

I am solving a problem where a set of N K-bit integers is given (N <= 10^4, K <= 50). I am allowed to do a single operation: choose two numbers A,B from the set and insert A xor B into the set.

The problem asks if it is possible, for the given set, to generate all numbers from 0 to 2K - 1 using only this operation, as many times as i want.

I read that this can be solved using Gaussian Elimination, but i don't know how to do it. Can any one help me with this problem? Thx in advance :)

EDIT : I solved the problem. Thanks to Enchom for the awesome algorithm! To the ones interested, here are the original problem statement and my solution:

https://www.urionlinejudge.com.br/judge/en/problems/view/1942

http://pastebin.com/aXmLB8Ud

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

Comments Comments (9)
| Write comment?
»
9 years ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like it

This is a famous problem. You can generate a smaller set of numbers that has the same properties as your initial set of numbers. This new smaller set mustn't have two numbers that have their most significant bit at the same place. You can build it in the following manner:

Start with an empty set, adding the initial numbers one by one. Suppose at some point we're adding some number P.

  1. Find the most significant bit of P
  2. If there is a number in the current set that has its most significant bit at the same position, XOR P by this number and go back to 1. Otherwise go to 3.
  3. If P is 0 then don't add it, otherwise add it to the set.

It is simple to see that the set you get as a result will never have two numbers with most significant bit at the same spot. Additionally you can see that any number that can be produced by XORing the values initially given to you can also be produced by XORing the values in this newly formed set. What is nice about this new set is that if you take any subset and XOR it you get a unique number. So it turns out that if your new set is of size T then you can form exactly 2T numbers by XORing.

Hence to solve your problem just check whether the resulting set is of size K.

There might be a simpler solution but the generation of this new set is actually extremely handy for many problems regarding XORing some set of numbers.

P.S.

I'm really tired so excuse me if this explanation is bad

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

    Thanks for the explanation!

    I noticed a similar property before i created this post : If i could generate the set {1000...0,0100...0,0010...0,...,0000...1} from the initial set, then i could generate all the 2^K numbers. But i had no idea how to check whether it is possible to generate this set. Now i have a simple algorithm to do it. Thanks one more time :)

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

    If the size of the new set is T, it's not guaranteed that you can form 2T numbers. In other words, we can't get the number 0 because no number would be able to cancel the leftmost bit of the biggest number in the set. I think that if in some moment of your method P reaches 0 and the size of the final set is T, then you can form 2T numbers.

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

      You can always get 0 if N ≥ 1. Just xor a number with itself.

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

        But if it's not allowed to xor same numbers, you have to check explicitly for 0. A problem in the Brazilian subregionals (maybe the same one OP is trying to solve) got a lot of teams with that trick.

        Edit: True, it's impossible with this specific statement. But it's still a valid warning because it applies to the (identical otherwise) statement that allows you to take any non-empty subset of the original set and xor it.

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

          How can you possibly get 0 without xoring the same number? I'm pretty sure you can't (as it's invertible). Nonetheless, this is a corner case and it is easy to treat. Just check for 0, as you said.

          The problem statement in this case did not mention that a and b have to be different.

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

            I forgot to mention this, i can't xor the same number, unless it appears twice in the input. Also , another way to get 0, is if 0 is already given in the input set.

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

          Yeah, it's exactly the Lottery problem u.u I asked other teams that solved it during the contest and they pointed Gaussian Elimination, but it looked like magic to me. So i tried to build a solution by myself and reduced the problem to this one i posted here :)

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

Auto comment: topic has been updated by skavurskaa (previous revision, new revision, compare).

→ Reply