UniformingMatrix | Topcoder Archive

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".

Definition

Class:: UniformingMatrix
Method:: isPossible
Parameters:: String[]
Returns:: String
Method signature:: String isPossible(String[] M)
(be sure your method is public)

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'.

Examples

```
{"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"

{"0110011",
 "1011000",
 "0101000",
 "0010001",
 "1010011",
 "1011011",
 "0111100"}

Returns: "impossible"

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.