PROBLEM STATEMENT
A binary matrix is a matrix in which each element is either 0 or 1. There is a secret binary
matrix with R rows and C columns. Your task is to determine its elements from two partial
descriptions.
The first description is given as a vector rows with R elements. Each element of rows
will be a string of C characters. Element i of rows describes the i-th row of the secret matrix.
Each character in each element of rows is either '0', '1', or '?'. The meaning of '?' is that the
corresponding element of the matrix may be either 0 or 1.
The second description is given as a vector columns with C elements. Each element of
columns will be a string of R characters. Each element of columns describes one column of the
secret matrix. Different elements of columns represent different columns, but not necessarily in
the correct order. Again, each character in each element of columns is either '0', '1', or '?'.
You may assume that there is at least one binary matrix that corresponds to both descriptions: its
rows match the elements of rows (in the same order) and its columns match the elements of columns
(after a suitable permutation is applied on columns). Your method must find the lexicographically
smallest of all such matrices. Return that matrix formatted as a vector .
DEFINITION
Class:P8XMatrixRecovery
Method:solve
Parameters:vector , vector
Returns:vector
Method signature:vector solve(vector rows, vector columns)
NOTES
-Given two different matrices A and B, let i be the first row on which they differ, and let j be
the first element in that row on which they differ. If A[i,j] < B[i,j], we say that A is
lexicographically smaller than B, and vice versa.
CONSTRAINTS
-rows will contain between 1 and 30 elements, inclusive.
-Each element of rows will contain between 1 and 30 characters, inclusive.
-All the elements of rows will contain the same number of character.
-Each character in each element of rows will be either '0', '1', or '?'.
-columns will contain exactly C elements, where C is the number of elements in rows[0].
-Each element of columns will contain exactly R characters, where R is the number of elements in
rows.
-Each character in each element of columns will be '0', '1', or '?'.
-There will be at least one binary matrix that corresponds to both rows and columns in the way
described in the problem statement.
EXAMPLES
0)
{"10?"
,"?11"}
{"01"
,"10"
,"1?"}
Returns: {"101", "011" }
Note that columns[0] describes column 1 of the secret matrix, columns[1] describes column 0 and
columns[2] describes column 2.
1)
{"0"
,"?"
,"1"}
{"0?1"}
Returns: {"0", "0", "1" }
There are two matrices that match both descriptions. We return the lexicographically smaller one.
2)
{"10"
,"01"}
{"10"
,"01"}
Returns: {"10", "01" }
3)
{"??0"
,"11?"
,"?01"
,"1?1"}
{"1???"
,"?111"
,"0?1?"}
Returns: {"010", "110", "101", "101" }
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)2010, TopCoder, Inc. All rights reserved.