TopCoder problem "EvenOnes" used in TCO08 Qual 3 (Division I Level Three)

Problem Statement

You are given a rectangular matrix with odd numbers of rows and columns. Each cell of the matrix contains either 0 or 1. In one move, you can select any one row or column of the matrix and replace all 0's with 1's and all 1's with 0's in that row/column. Your aim is to have an even number of 1's in each row and each column.

The elements of the String[] matrix correspond to the rows of the matrix. Return the minimal number of moves needed to achieve your aim, or -1 if it's impossible.

Definition

Class:	EvenOnes
Method:	minOperations
Parameters:	String[]
Returns:	int
Method signature:	int minOperations(String[] matrix)
(be sure your method is public)

Constraints

matrix will contain between 1 and 49 elements, inclusive.

Each element of matrix will contain between 1 and 49 characters, inclusive.

All elements in matrix will contain the same number of characters.

The number of elements in matrix will be odd.

The number of characters in each element of matrix will be odd.

Each character in each element of matrix will be '0' (zero) or '1' (one).

Examples

{
 "111",
 "011",
 "001"
}

Returns: 2

We can first apply the operation to the middle row of the matrix, and then to the middle column.

{
  "111",
  "111",
  "111",
  "111",
  "111"
}

Returns: 3

We must apply the operations either to all rows or to all columns. As the number of columns is less than the number of rows, we choose the second variant.

{
  "00000",
  "00000",
  "00000"
}

Returns: 0

The matrix initially contains an even number of ones in each row and column, so we don't apply any operations.

{
  "10101",
  "01010",
  "10101",
  "01010",
  "10101"
}

Returns: 5

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8018

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=12058&pm=8018

Writer:

ivan_metelsky

Testers:

PabloGilberto , vorthys , Olexiy , misof

Problem categories:

Simple Math