P8XMatrixRecovery

SRM 527 · 2011-05-25 · by dolphinigle

SRM 527 · 2011-05-25 · by dolphinigle · Graph Theory

Show categories

Class Name: P8XMatrixRecovery

Return Type: String[]

Method Name: solve

Arg Types: (vector<string>, vector<string>)

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 String[] 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 String[] 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 String[].

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] &lt 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

{"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.

{"0"
,"?"
,"1"}
{"0?1"}
Returns: {"0", "0", "1" }

There are two matrices that match both descriptions. We return the lexicographically smaller one.

{"10"
,"01"}
{"10"
,"01"}
Returns: {"10", "01" }

{"?"}
{"?"}
Returns: {"0" }

{"??????????????????????????????"
,"??????????????????????????????"
,"??????????????????????????????"
,"??????????????????????????????"
,"??????????????????????????????"
,"??????????????????????????????"
,"??????????????????????????????"
,"??????????????????????????????"
,"??????????????????????????????"
,"??????????????????????????????"
,"??????????????????????????????"
,"??????????????????????????????"
,"??????????????????????????????"
,"??????????????????????????????"
,"??????????????????????????????"
,"??????????????????????????????"
,"??????????????????????????????"
,"??????????????????????????????"
,"??????????????????????????????"
,"??????????????????????????????"
,"??????????????????????????????"
,"??????????????????????????????"
,"??????????????????????????????"
,"??????????????????????????????"
,"??????????????????????????????"
,"??????????????????????????????"
,"??????????????????????????????"
,"??????????????????????????????"
,"??????????????????????????????"
,"??????????????????????????????"}
{"??????????????????????????????"
,"??????????????????????????????"
,"??????????????????????????????"
,"??????????????????????????????"
,"??????????????????????????????"
,"??????????????????????????????"
,"??????????????????????????????"
,"??????????????????????????????"
,"??????????????????????????????"
,"??????????????????????????????"
,"??????????????????????????????"
,"??????????????????????????????"
,"??????????????????????????????"
,"??????????????????????????????"
,"??????????????????????????????"
,"??????????????????????????????"
,"??????????????????????????????"
,"??????????????????????????????"
,"??????????????????????????????"
,"??????????????????????????????"
,"??????????????????????????????"
,"??????????????????????????????"
,"??????????????????????????????"
,"??????????????????????????????"
,"??????????????????????????????"
,"??????????????????????????????"
,"??????????????????????????????"
,"??????????????????????????????"
,"??????????????????????????????"
,"??????????????????????????????"}
Returns: {"000000000000000000000000000000", "000000000000000000000000000000", "000000000000000000000000000000", "000000000000000000000000000000", "000000000000000000000000000000", "000000000000000000000000000000", "000000000000000000000000000000", "000000000000000000000000000000", "000000000000000000000000000000", "000000000000000000000000000000", "000000000000000000000000000000", "000000000000000000000000000000", "000000000000000000000000000000", "000000000000000000000000000000", "000000000000000000000000000000", "000000000000000000000000000000", "000000000000000000000000000000", "000000000000000000000000000000", "000000000000000000000000000000", "000000000000000000000000000000", "000000000000000000000000000000", "000000000000000000000000000000", "000000000000000000000000000000", "000000000000000000000000000000", "000000000000000000000000000000", "000000000000000000000000000000", "000000000000000000000000000000", "000000000000000000000000000000", "000000000000000000000000000000", "000000000000000000000000000000" }

Submissions are judged against all 151 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class P8XMatrixRecovery with a public method vector<string> solve(vector<string> rows, vector<string> columns) · 151 test cases · 2 s / 256 MB per case