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 $2^K-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 [user:ImAlsoGay,2016-04-01] 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
↵
The problem asks if it is possible, for the given set, to generate all numbers from 0 to $2^K-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 [user:ImAlsoGay,2016-04-01] 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
