Statistics

Problem Statement for "TheMagicMatrix"

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 an int 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.

Definition

Class:
TheMagicMatrix
Method:
find
Parameters:
int, int[], int[], int[]
Returns:
int
Method signature:
int find(int n, int[] rows, int[] columns, int[] values)
(be sure your method is public)

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

  1. 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.

  2. 2

    {0, 1}

    {1, 0}

    {4, 7}

    Returns: 0

  3. 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

  4. 474

    {44, 77}

    {47, 74}

    {4, 7}

    Returns: 83494518

  5. 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

  6. 4

    {0, 0, 0, 1, 2, 2, 2, 3, 3, 3}

    {0, 1, 3, 2, 0, 1, 3, 0, 1, 3}

    {0, 8, 7, 5, 4, 7, 8, 6, 6, 5}

    Returns: 2

  7. 4

    {0, 1, 1, 1, 2, 2, 2, 3, 3, 3}

    {3, 0, 1, 2, 0, 1, 2, 0, 1, 2}

    {8, 5, 0, 8, 1, 0, 4, 6, 7, 9}

    Returns: 2

  8. 4

    {0, 1, 1, 1, 2, 2, 2, 3, 3, 3}

    {2, 0, 1, 3, 0, 1, 3, 0, 1, 3}

    {1, 0, 7, 4, 5, 6, 7, 7, 4, 9}

    Returns: 2

  9. 4

    {0, 0, 0, 1, 2, 2, 2, 3, 3, 3}

    {0, 2, 3, 1, 0, 2, 3, 0, 2, 3}

    {6, 8, 1, 8, 3, 7, 5, 3, 0, 1}

    Returns: 2

  10. 4

    {0, 0, 0, 1, 1, 1, 2, 3, 3, 3}

    {0, 2, 3, 0, 2, 3, 1, 0, 2, 3}

    {0, 5, 2, 3, 4, 3, 7, 8, 5, 3}

    Returns: 2

  11. 696

    {59, 376, 30, 164, 223}

    {474, 576, 190, 123, 445}

    {2, 5, 4, 7, 3}

    Returns: 485257912

  12. 213

    {73, 154, 64, 172, 156, 182}

    {163, 190, 146, 3, 113, 41}

    {9, 4, 9, 5, 7, 3}

    Returns: 1165138081

  13. 926

    {849}

    {711}

    {1}

    Returns: 226306916

  14. 521

    {11, 290, 325, 47, 519, 430, 164, 375, 360, 476}

    {205, 3, 432, 51, 27, 516, 162, 344, 102, 410}

    {1, 6, 4, 6, 2, 9, 0, 3, 9, 4}

    Returns: 1131837525

  15. 517

    {240, 291, 513, 310, 431, 29}

    {45, 309, 404, 494, 423, 189}

    {1, 2, 3, 7, 7, 1}

    Returns: 278199414

  16. 809

    {698, 489, 477, 302, 468, 61, 770}

    {221, 148, 101, 492, 636, 700, 331}

    {3, 3, 7, 8, 5, 8, 4}

    Returns: 764991183

  17. 23

    {2, 6, 16, 22}

    {15, 12, 12, 0}

    {9, 4, 5, 1}

    Returns: 614143248

  18. 489

    {443, 214, 303, 124, 337, 133}

    {47, 386, 10, 23, 196, 156}

    {1, 3, 4, 7, 1, 9}

    Returns: 999008111

  19. 199

    {73, 57, 81, 170, 21, 183}

    {158, 53, 109, 36, 52, 194}

    {0, 4, 9, 6, 6, 1}

    Returns: 723636004

  20. 449

    {240, 283, 105, 31, 334}

    {6, 420, 295, 27, 410}

    {7, 0, 9, 9, 3}

    Returns: 1139177212

  21. 2

    {1, 0, 0, 1}

    {1, 0, 1, 0}

    {3, 5, 7, 2}

    Returns: 0

  22. 6

    {1, 5, 3, 3, 2, 3, 2, 0}

    {4, 1, 5, 1, 3, 3, 2, 1}

    {7, 3, 2, 4, 6, 6, 7, 3}

    Returns: 882592654

  23. 10

    {8, 1, 7, 0, 0, 9, 2}

    {5, 4, 8, 5, 2, 5, 1}

    {6, 5, 3, 7, 4, 3, 1}

    Returns: 947175191

  24. 6

    {3, 1, 2, 0, 1, 3}

    {4, 3, 4, 2, 0, 3}

    {0, 6, 3, 3, 6, 9}

    Returns: 604945139

  25. 3

    {2, 1, 0, 2, 0}

    {0, 1, 2, 1, 0}

    {1, 5, 6, 7, 7}

    Returns: 0

  26. 6

    {4, 2, 3, 5, 0, 1}

    {4, 2, 3, 5, 0, 1}

    {1, 6, 2, 2, 5, 4}

    Returns: 604945139

  27. 10

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

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

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

    Returns: 863910131

  28. 5

    {1, 0, 2, 3, 4}

    {1, 0, 2, 3, 4}

    {5, 1, 9, 6, 4}

    Returns: 8290

  29. 9

    {2, 5, 0, 1, 3, 8, 7, 4, 6}

    {2, 5, 0, 1, 3, 8, 7, 4, 6}

    {1, 2, 1, 0, 6, 4, 0, 3, 3}

    Returns: 723575322

  30. 1

    {0}

    {0}

    {6}

    Returns: 1

  31. 5

    {0, 0, 1, 4, 2, 2, 1, 3, 1, 3}

    {4, 3, 3, 2, 4, 2, 2, 0, 4, 2}

    {5, 6, 1, 1, 3, 1, 6, 5, 1, 3}

    Returns: 10000000

  32. 5

    {2, 2, 1, 3, 0, 3, 0, 4, 1, 2}

    {0, 3, 4, 4, 2, 1, 4, 3, 0, 4}

    {9, 5, 8, 8, 1, 4, 1, 9, 3, 7}

    Returns: 10000000

  33. 5

    {2, 2, 1, 1, 3, 0, 2, 4, 1, 2}

    {2, 4, 2, 0, 0, 4, 0, 4, 4, 3}

    {0, 7, 0, 8, 6, 4, 9, 3, 0, 0}

    Returns: 10000000

  34. 4

    {3, 1, 1, 1, 0, 3, 3, 2, 0, 1}

    {0, 0, 2, 3, 0, 1, 2, 1, 2, 1}

    {7, 8, 7, 8, 6, 7, 8, 8, 4, 4}

    Returns: 1

  35. 4

    {3, 1, 2, 0, 3, 3, 2, 0, 0, 1}

    {0, 2, 3, 0, 2, 1, 2, 3, 1, 1}

    {1, 5, 7, 5, 5, 7, 1, 9, 3, 2}

    Returns: 0

  36. 1000

    {532, 584, 256, 230, 51, 44, 913, 487, 468, 596}

    {372, 416, 829, 198, 482, 836, 542, 461, 275, 555}

    {9, 5, 1, 4, 2, 0, 1, 3, 5, 7}

    Returns: 464378797

  37. 1000

    {584}

    {416}

    {5}

    Returns: 849700252

  38. 2

    {1, 0, 0, 1}

    {1, 0, 1, 0}

    {7, 7, 7, 7}

    Returns: 1

  39. 3

    {0, 2, 2, 0, 1, 0, 1, 2, 1}

    {0, 2, 1, 1, 2, 2, 1, 0, 0}

    {4, 4, 4, 4, 4, 4, 4, 4, 4}

    Returns: 1

  40. 5

    {4, 3, 3, 4, 0, 3, 2, 2, 2, 2}

    {1, 1, 0, 0, 4, 2, 2, 4, 1, 3}

    {6, 6, 4, 5, 4, 5, 7, 5, 4, 7}

    Returns: 10000000

  41. 5

    {0, 4, 2, 3, 0, 2, 4, 2, 4, 0}

    {3, 2, 1, 3, 2, 2, 4, 0, 1, 4}

    {5, 4, 7, 7, 4, 4, 5, 4, 4, 5}

    Returns: 10000000

  42. 5

    {2, 1, 4, 0, 0, 4, 0, 0, 4, 3}

    {0, 0, 3, 3, 1, 2, 2, 4, 1, 0}

    {7, 7, 4, 7, 7, 4, 7, 4, 4, 6}

    Returns: 10000000

  43. 7

    {1, 1, 5, 0, 4, 4, 0, 3, 1, 5}

    {5, 0, 1, 6, 2, 0, 1, 4, 3, 6}

    {7, 6, 6, 7, 6, 6, 6, 4, 4, 6}

    Returns: 822865995

  44. 5

    {4, 2, 4, 1, 1, 2, 0, 0, 3, 1}

    {3, 2, 0, 3, 1, 4, 0, 2, 0, 0}

    {4, 5, 7, 7, 6, 5, 6, 6, 5, 6}

    Returns: 10000000

  45. 9

    {6, 0, 3, 4, 1, 2, 7, 5, 8, 8}

    {6, 0, 3, 4, 1, 2, 7, 5, 8, 0}

    {3, 5, 2, 1, 4, 6, 7, 2, 1, 7}

    Returns: 1060011845

  46. 8

    {3, 0, 1, 1, 7, 0, 5, 6, 4, 2}

    {3, 5, 7, 1, 7, 0, 5, 6, 4, 2}

    {4, 1, 7, 7, 8, 1, 7, 6, 2, 0}

    Returns: 776736186

  47. 8

    {4, 6, 2, 2, 7, 1, 5, 0, 6, 3}

    {4, 4, 4, 2, 7, 1, 5, 0, 6, 3}

    {0, 3, 4, 2, 2, 3, 4, 6, 9, 3}

    Returns: 776736186

  48. 474

    {44, 77 }

    {47, 74 }

    {4, 7 }

    Returns: 83494518

  49. 10

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

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

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

    Returns: 863910131

  50. 10

    {0, 0, 0, 1, 1, 1, 2, 2, 3, 3 }

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

    {3, 4, 5, 6, 7, 8, 3, 4, 7, 8 }

    Returns: 863910131

  51. 10

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

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

    {1, 4, 3, 5, 6, 8, 6, 4, 5, 0 }

    Returns: 863910131

  52. 1000

    {6, 3, 7, 2, 5, 1, 6, 5, 9, 3 }

    {7, 7, 1, 7, 8, 3, 0, 5, 8, 1 }

    {7, 7, 6, 1, 0, 1, 1, 4, 0, 5 }

    Returns: 464378797

  53. 1000

    {0, 0, 0, 500, 500, 700, 999, 999, 999, 999 }

    {5, 6, 7, 6, 7, 5, 6, 7, 3, 8 }

    {2, 3, 4, 5, 0, 3, 1, 2, 3, 5 }

    Returns: 464378797

  54. 4

    {0, 0, 1, 1, 2, 2, 3, 3 }

    {0, 1, 0, 1, 2, 3, 2, 3 }

    {0, 0, 0, 0, 0, 0, 0, 0 }

    Returns: 1000

  55. 5

    {0, 0, 0, 0, 0, 1, 1, 1, 1, 1 }

    {0, 1, 2, 3, 4, 0, 1, 2, 3, 4 }

    {8, 0, 5, 4, 0, 8, 8, 0, 7, 9 }

    Returns: 0

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)2024, TopCoder, Inc. All rights reserved.
This problem was used for: