TheMagicMatrix
TCO13 Round 2A · 2013-02-19 · by Vasyl[alphacom]
TCO13 Round 2A · 2013-02-19 · by Vasyl[alphacom] · Math
Problem Statement
Problem Statement
A magic matrix is a square matrix filled with digits (0 to 9) such that its row sums and column sums all have the same last digit.
John has n by n matrix.
Its rows and columns are numbered from 0 to n-1.
Some cells of the matrix already contain digits and some are empty.
John wants to assign a value to each empty cell to get a magic matrix.
You are given anint n and int[] s rows, columns, values.
The number values[i] is the digit in John's matrix at row rows[i] and at column columns[i].
Return the number of different matrices John can get modulo 1,234,567,891.
You are given an
Constraints
- n will be between 1 and 1000, inclusive.
- rows will contain between 1 and 10 elements, inclusive.
- rows, columns and values will all contains the same number of elements.
- Each element of rows will be between 0 and n-1, inclusive.
- Each element of columns will be between 0 and n-1, inclusive.
- Each element of values will be between 0 and 9, inclusive.
- All pairs (rows[i], columns[i]) will be distinct.
Examples
0)
2
{0, 1}
{1, 0}
{4, 4}
Returns: 10
John will get a magic matrix only if he assigns equal values to both empty cells.
1)
2
{0, 1}
{1, 0}
{4, 7}
Returns: 0
2)
4
{0, 0, 0, 1, 2, 2, 2, 3, 3, 3}
{0, 1, 2, 3, 0, 1, 2, 0, 1, 2}
{3, 5, 1, 9, 5, 1, 8, 6, 7, 1}
Returns: 2
3)
474
{44, 77}
{47, 74}
{4, 7}
Returns: 83494518
4)
4
{0, 0, 0, 1, 1, 1, 2, 3, 3, 3}
{1, 2, 3, 1, 2, 3, 0, 1, 2, 3}
{6, 2, 8, 4, 9, 8, 0, 7, 3, 7}
Returns: 2
Submissions are judged against all 55 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class TheMagicMatrix with a public method int find(int n, vector<int> rows, vector<int> columns, vector<int> values) · 55 test cases · 2 s / 256 MB per case