TopCoder problem "SumOfSelectedCells" used in SRM 360 (Division I Level One , Division II Level Two)

Problem Statement

There is a rectangular table with an integer written in each cell.

Later, Jessie will come and select some cells in such a way that each row and each column contains no more than one selected cell. She will always select the maximum possible number of cells. However, there might be several possible selections of that size.

Larry suggested a hypothesis: "No matter what maximum selection Jessie choses, the sum of the numbers in the selected cells will always be the same."

Given a String[] table, check whether Larry's hypothesis is correct and return "CORRECT" or "INCORRECT" (quotes for clarity only).

Definition

Class:	SumOfSelectedCells
Method:	hypothesis
Parameters:	String[]
Returns:	String
Method signature:	String hypothesis(String[] table)
(be sure your method is public)

Constraints

table will contain between 1 and 20 elements, inclusive.

Each element of table will be contain between 1 and 50 characters, inclusive.

Each element of table will be a space-separated list of integers.

Each element of table will contain the same number of entries.

Each element of table will contain between 1 and 20 entries, inclusive.

All numbers in the table will be between 1 and 50, inclusive, with no leading zeroes.

Examples

{"5 6 6"}

Returns: "INCORRECT"

Jessie will select exactly one cell. The sum will be either 5 or 6.

{"11 12 13 14",
 "21 22 23 24",
 "31 32 33 34",
 "41 42 43 44"}

Returns: "CORRECT"

There are 4! = 24 possible selections for Jessie, but it can be shown that each of them gives the sum of 1 + 2 + 3 + 4 + 10 + 20 + 30 + 40 = 110.

{"3 7",
 "3 7",
 "3 7"}

Returns: "CORRECT"

Jessie will select exactly one 3 and exactly one 7 giving a total of 10.

{"1 2 3",
 "4 5 6",
 "9 8 7"}

Returns: "INCORRECT"

Jessie can get 13 (2 + 4 + 7) or 15 (1 + 6 + 8) or 17 (3 + 5 + 9).

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10772&pm=7875

Writer:

darnley

Testers:

PabloGilberto , Olexiy , lovro , ivan_metelsky

Problem categories:

Math