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
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.
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
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 :)
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.
You can always get 0 if N ≥ 1. Just xor a number with itself.
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.
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.
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.
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 :)
Auto comment: topic has been updated by skavurskaa (previous revision, new revision, compare).