UniformingMatrix
TCO19 SRM 744 · 2018-12-13 · by boba5551
Problem Statement
You are given a matrix M consisting of zeros and ones. You are allowed to perform operations of the following type:
- Choose a position (i, j) in the matrix.
- Flip all the values but M(i, j) in the i-th row of M. By flipping, '0' becomes '1' and '1' becomes '0'. Note that M(i, j) does not get changed.
- Flip all the values but M(i, j) in the j-th column of M. Note that M(i, j) does not get changed.
Output "possible" if it is possible to transform M to an all ones matrix by applying any number of these operations. Otherwise, output "impossible".
Notes
- Note that the return value is case-sensitive.
Constraints
- M will contain between 1 and 100 elements, inclusive.
- Each elements of M will contain between 1 and 100 characters, inclusive.
- All the elements of M will contain the same number of characters.
- Each character of each element of M will be '0' or '1'.
{"0"}
Returns: "impossible"
The only operation it is possible to apply here is on M(0, 0). However, this operation does not change the value M(0, 0), and hence there is no way to obtain all ones matrix.
{"1101",
"0010"}
Returns: "possible"
One possibility here is to apply the operation on M(1, 2).
{"11111",
"11111",
"11111",
"11111",
"11111",
"11111",
"11111",
"11111"}
Returns: "possible"
The input matrix is already in the required format, so there is no need to apply any operation in this case.
{"110",
"001",
"110"}
Returns: "possible"
It is possible to obtain the all ones matrix from the input by applying the operations on M(2, 1), M(2, 2) and M(1, 1). For instance, applying the operation on M(2, 1) leads to matrix 100 011 011
{"01010",
"10101",
"01010",
"01010"}
Returns: "possible"
Submissions are judged against all 99 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class UniformingMatrix with a public method string isPossible(vector<string> M) · 99 test cases · 2 s / 256 MB per case