Problem: You are given a set of n numbers, C = { c_1, c_2, ..., c_n}and you have to find the minimum size of subset of C from which you can create the given n numbers by only doing xor operations on the elements of the subset.
Solution: One starts by thinking about the properties of XOR. There are only a few properties that I know, like x + y + x = y ( I'll represent XOR by + through out the post). So, I have to find a subset V = { v_1, v_2,...,v_k} such that a_i1*v_1+a_i2*v_2+...+a_ik*v_k = c_i, for all elements of C and a_ij are either 0 or 1. This looks similat to c_i being linear combination of V. So, we check if there is a vector space with XOR as the addition operation and voilà, if a euclidean vector space is over the field Z_2, then addition operation is x+y % 2 which is the definition of XOR. So, now all we need to find is the rank of matrix [c_1 c_2 ...c_n] . To find the rank reduced matrix by elementary operations (gauss elimination)
Source: Rishab Vaid who read it perhaps on Topcoder
Solution: One starts by thinking about the properties of XOR. There are only a few properties that I know, like x + y + x = y ( I'll represent XOR by + through out the post). So, I have to find a subset V = { v_1, v_2,...,v_k} such that a_i1*v_1+a_i2*v_2+...+a_ik*v_k = c_i, for all elements of C and a_ij are either 0 or 1. This looks similat to c_i being linear combination of V. So, we check if there is a vector space with XOR as the addition operation and voilà, if a euclidean vector space is over the field Z_2, then addition operation is x+y % 2 which is the definition of XOR. So, now all we need to find is the rank of matrix [c_1 c_2 ...c_n] . To find the rank reduced matrix by elementary operations (gauss elimination)
Source: Rishab Vaid who read it perhaps on Topcoder
No comments:
Post a Comment