TopCoder problem "BinaryMatrix" used in TCO08 Semifinal 1 (Division I Level Three)

Problem Statement

You are given a binary rectangular matrix with exactly five columns. A matrix is called good if it contains exactly columns[i] ones in the i-th column. To make the matrix good, you are allowed to perform at most maxMoveCount moves. With each move, you select a row of the matrix and circularly shift it to the right by 1 position (so, for example, row {0, 0, 1, 0, 0} becomes {0, 0, 0, 1, 0}).

Given matrix, columns and maxMoveCount, return the lexicographically greatest good matrix you can achieve. If you can not achieve any good matrix, return an empty String[]. To compare two matrices lexicographically, concatenate all rows starting from the top for each of the matrices and compare the resulting strings. String A is lexicographically greater than string B if it contains the bigger character at the first position where they differ.

Definition

Class:	BinaryMatrix
Method:	getMaximalLexicographically
Parameters:	String[], int[], int
Returns:	String[]
Method signature:	String[] getMaximalLexicographically(String[] matrix, int[] columns, int maxMoveCount)
(be sure your method is public)

Constraints

matrix will contain between 1 and 40 elements, inclusive.

Each element of matrix will contain exactly five digits.

Each element of matrix will contain only digits '0' or '1'.

columns will contain exactly five elements.

Each element of columns will be between 0 and 40, inclusive.

maxMoveCount will be between 0 and 160, inclusive.

Examples

{"01000", "10000"}

{1,1,0,0,0}

Returns: {"10000", "01000" }

Shift the first row 4 times and the second row once.

{"01000", "10000"}

{1,1,0,0,0}

Returns: {"01000", "10000" }

Don't change anything.

{"00100", "10000", "00010", "00001", "01000"}

{1,1,1,1,1}

Returns: {"10000", "01000", "00010", "00001", "00100" }

{"00011","00010","11000"}

{0,1,2,2,0}

Returns: {"01100", "00010", "00110" }

{"00000","11111"}

{5,0,0,0,0}

Returns: { }

{"00011"}

{0,1,0,1,0}

Returns: { }

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=12015&pm=8781

Writer:

Mike Mirzayanov

Testers:

PabloGilberto , SnapDragon , Olexiy , ivan_metelsky