XORing
TCO05 Wildcard · 2005-08-16 · by lars2520
TCO05 Wildcard · 2005-08-16 · by lars2520 · Brute Force
Problem Statement
Problem Statement
Consider a matrix with n columns, given by m, where mi,j is represented by character j of element i of m. We would like to find some function, f, such that for all i:
f(mi,0,mi,1,...,mi,n-1) = ti.
All elements of the matrix are binary 0's and 1's, as are the elements of t. Furthermore, the function must take on the form:
a0*mi,0 ^ a1*mi,1 ^ ... ^ an-1mi,n-1, where each aj is either 0 or 1 and '^' represents the XOR operation. In other words, the function takes a row of the matrix, and XORs some subset of the elements of that row to get the target from t. Your task is to return how many distinct functions (choices of ai's) give the correct target for each i.
f(mi,0,mi,1,...,mi,n-1) = ti.
All elements of the matrix are binary 0's and 1's, as are the elements of t. Furthermore, the function must take on the form:
a0*mi,0 ^ a1*mi,1 ^ ... ^ an-1mi,n-1, where each aj is either 0 or 1 and '^' represents the XOR operation. In other words, the function takes a row of the matrix, and XORs some subset of the elements of that row to get the target from t. Your task is to return how many distinct functions (choices of ai's) give the correct target for each i.
Constraints
- m and t will contain the same number of elements.
- m and t will contain between 1 and 50 elements, inclusive.
- Each element of m will contain the same number of characters.
- Each element of m will contain between 1 and 50 characters, inclusive.
- Each character in m will be '0' or '1'.
- Each element of t will be 0 or 1.
Examples
0)
{"000",
"001",
"010"}
{0,1,1}
Returns: 2
1)
{"000",
"001",
"010"}
{1,1,1}
Returns: 0
2)
{"0000",
"0000",
"0000"}
{0,0,0}
Returns: 16
3)
{
"0000000000000000000000000000000000000000",
"0000000000000000000000000000000000000000",
"0000000000000000000000000000000000000000",
"0000000000000000000000000000000000000000",
"0000000000000000000000000000000000000000"}
{0,0,0,0,0}
Returns: 1099511627776
4)
{"000000",
"000000",
"000000"}
{0,0,0}
Returns: 64
Submissions are judged against all 65 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class XORing with a public method long long findSubset(vector<string> m, vector<int> t) · 65 test cases · 2 s / 256 MB per case