PARITY - Parity
You are given n binary strings s1 ... sn, each of the same length m. Along with each si you are given a bit bi. 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 bi is the XOR of the bits of si at the indices in S. The si 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 s1 = 1010 and S = {0, 3}, then b1 would be 1 (the first bit of s1) XOR'd with 0 (the last bit of s1), which is 1. Given n, k, and the strings s1 ... sn and their corresponding bi, find a set S of size at most k which produces the given bi. You should also detect when no such S exists.
Input
The first line contains n and k, space-separated (1 ≤ n ≤ 64, 0 ≤ k ≤ 10). n lines then follow, where the ith line contains si, followed by a space, then bi. In a given test case all strings si are of the same length m (1 ≤ m ≤ 50). k will not be bigger than m.
Output
If no set S of size at most k exists producing the given bi, output -1 followed by a newline. Otherwise, on the first line output the size of a possible S. If the size of that S is not 0, on the second line, output a space-separated list of the indices in S, followed by a newline. If there exist multiple valid S to be output, you can output any one of your choosing.
Example
Input: 3 1 111 1 001 0 011 1 Output: 1 1
hide comments
khan_cse_ruet:
2021-06-20 13:39:21
1. This problem shows WA after all case(33) , even your 1st case is wrong.
|
|
Scape:
2016-07-30 23:30:36
Thanks guys! |
|
Francky:
2016-07-20 14:29:27
Issue fixed, and rejudge in progress ; thanks @admins.
|
|
Scape:
2016-07-18 01:11:08
Please fix Internal Error and rejudge all submissions. Thanks!
|
|
One Two Three:
2015-06-22 15:45:31
I got Internal Error submitting the solution, please fix it! |
|
Marcel Stockli:
2012-04-12 21:24:23
somebody has problems with the case 33? I always got WA in that case. |
Added by: | Minilek |
Date: | 2008-12-22 |
Time limit: | 5s-30s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |
Resource: | MIT Individual Contest 2008 |