TopCoder problem "PositiveArray" used in TCHS SRM 50 (Division I Level Three)

Problem Statement


A two-dimensional array of integers is positive if the sum of all elements in each row and each column is strictly greater than zero.

For example, the following array is positive:

 2  1 -1
-1  2  2

, while the next one is not:

 1  1 -1
-1  2  2

(the sum of the elements in the first column is 0).

You will be given a String[] data, representing a 2-d array. The j-th character of the i-th element of data represents the j-th number in the i-th row of the array. Digits ('0'-'9') denote numbers between 0 and 9, lowercase letters ('a'-'z') denote numbers between 10 and 35, respectively, and uppercase letters ('A'-'Z') denote negative numbers between -1 and -26, respectively. For example, 'a' represents 10, 'c' represents 12, 'A' represents -1 and 'Z' represents -26.

In one move you are allowed to change the signs of all numbers in some row or column (i.e., multiply all numbers in a row or in a column by -1). Return the minimal number of moves you'll need to get a positive array, or -1 if this is impossible.



Method signature:int countMoves(String[] data)
(be sure your method is public)


-data will contain between 1 and 18 elements, inclusive.
-Each element of data will contain between 1 and 18 characters, inclusive.
-Each element of data will contain only digits ('0'-'9') or letters ('a'-'z', 'A'-'Z').
-All elements of data will have the same length.


Returns: 0
The input array is already positive.
Returns: 1
We change signs in the last column and get a positive array.
Returns: 2
We can not succeed with less than 2 moves. One of the possible solutions is to reverse the first row and the last column.
Returns: -1

Problem url:

Problem stats url:



PabloGilberto , Olexiy , ivan_metelsky

Problem categories:

Brute Force, Simple Math