mit-parity

You are given n binary strings s₁, ..., s_n, each of the same length m. Along with each s_i you are given a bit b_i. You are also given some nonnegative integer k and want to know whether there exists a subset S of {0, 1, . . . ,m−1} of size at most k such that for each i = 1, 2, . . . , n, the bit b_i is the XOR of the bits of s_i at the indices in S. The s_i are 0-indexed strings. Recall that the XOR of a set of bits is 1 if the number of bits equal to 1 is odd, else the XOR is 0 (in particular, the XOR of an empty set of bits is 0).

For example, if s₁ = 1010 and S = {0, 3}, then b₁ would be 1 (the first bit of s₁) XOR’d with 0 (the last bit of s₁), which is 1.

Given n, k, and the strings s₁, . . . , s_i and their corresponding b_i, find a set S of size at most k which produces the given b_i. You should also detect when no such S exists.