NumberGrid | Topcoder Archive

Problem Statement

NOTE: This problem statement contains subscripts that may not display properly if viewed outside of the applet.

A number grid is a rectangular matrix where each cell is a digit between 0 and 9, inclusive.

Given a number grid G, an encrypted grid E with the same dimensions can be generated using the following procedure (using zero-based indexing):

for(i=0;i&lt;rows;++i){
  for(j=0;j&lt;cols;++j){
    E_i,j = 0
    for(r=0;r&lt;rows;++r){
      for(c=0;c&lt;cols;++c){
        if( (r equals i) or (c equals j))
        {E_i,j = E_i,j + G_r,c}
      }
    }
  }
}

Note that this means each cell in E is the sum of all the cells in G that positionally share the same row or column. (The cell in G with both the same row and same column is only counted once.)

An example number grid G is given below:

-------------
| 0 | 1 | 3 |
-------------
| 2 | 5 | 7 |
-------------

Performing the above procedure yields the encrypted grid below:

----------------
| 6  | 9  | 11 |
----------------
| 14 | 15 | 17 |
----------------

The cell in row 0, column 1 of E, for example, is calculated by taking the sum of all cells in G with either row 0 or column 1 (0 + 1 + 3 + 5 = 9). Note that the '1' cell is counted only once.

Given an encrypted grid E, reconstruct the original number grid G if possible.

The encrypted grid is given in three separate String[]s. hundreds gives the digit in the hundreds place of each cell in the encrypted grid, tens gives the digit in the tens place, and ones gives the digit in the ones place. In each of these String[]s, the j-th character of the i-th element represents the cell in row i, column j.

For example, if the encrypted grid appeared as follows:

------------------
| 106 | 72  | 5  |
------------------
| 14  | 135 | 17 |
------------------

The input would appear like this:

hundreds

{"100",
 "010"}

tens

{"070",
 "131"}

ones

{"625",
 "457"}

If there is exactly one valid number grid G that yields the given encrypted grid, return a String[] representing G, where the j-th character of the i-th element is the digit in row i, column j. If there are no possible number grids, return a String[] containing exactly one element: "NO SOLUTIONS" (quotes for clarity only). If there are multiple distinct solutions, return a String[] containing exactly one element, formatted as "n SOLUTIONS" (quotes for clarity only), where n is the number of solutions modulo 1000000007 (10^9 + 7), with no extra leading zeroes.

Definition

Class:: NumberGrid
Method:: decrypt
Parameters:: String[], String[], String[]
Returns:: String[]
Method signature:: String[] decrypt(String[] hundreds, String[] tens, String[] ones)
(be sure your method is public)

Notes

Two number grids G1 and G2 are considered distinct if at least one entry in G1 is different from the corresponding entry in G2.

Constraints

hundreds will contain between 1 and 50 elements, inclusive.
Each element of hundreds will contain between 1 and 50 characters, inclusive.
Each element of hundreds will have the same number of characters.
Each element of hundreds will contain only digits ('0' - '9').
tens and ones will have the same number of elements as hundreds.
Each element of tens and ones will have the same number of characters as each element of hundreds.
Each element of tens and ones will contain only digits ('0' - '9').

Examples

{"000",
 "000"}

{"001",
 "111"}

{"691",
 "457"}

Returns: {"013", "257" }

The example given in the problem statement.

```
{"0"}
```
```
{"0"}
```
```
{"3"}
```
```
Returns: {"3" }
```
A single cell means that the solution is equal to the input...
```
{"0"}
```
```
{"4"}
```
```
{"2"}
```
```
Returns: {"NO SOLUTIONS" }
```
...unless the input would not be a valid number grid.

{"23333333333322333333333333333333333333333333333332",
"33333333343333333333333333333333334333333333443333",
"12222222222211221222222222222222222222222222222221",
"12222222222211221122222221111221222222112222222221",
"12222222222211221122222221111221222222112222222221",
"12222222222211221122222221111221222222112222222221",
"12222222222211221122222221111221222222112222222221",
"22222222232222222222222222222222223222222222232222",
"12222222222222222222222222222222222222222222232221",
"01111111111100110011111110000110111111001111111110",
"01111111111100110011111110000110111111001111111110",
"22222222232222222222222222222222223222222222332222",
"22222222232222222222222222222222222222222222232222",
"12222222222222222222222222222222222222222222222221",
"11111112221111111112221111111111112222111112222211",
"12221112222211221122222221111221222222112222222221",
"11111112222211111122221221111221222222111222222221",
"22222223333322322233332332222332333333222223333322",
"33333333343333333333333333333333333333333333343333",
"01111111111100110011111110000110111111001111111110",
"01111111111100110011111110000110111111001111111110",
"01111111111100110011111110000110111111001111111110"}

{"81221116682299220134442330000331447555001226795438",
"14554449915522553457764553333554770777335559027651",
"81221116682299229123331330011221336334111226783318",
"60110004461188118901120119999119225223990115672106",
"60110004461188118901120119999119225223990115672106",
"60110004461188118901120119999119225223990115672106",
"60110004461188118901120119999119225223990115572116",
"14554448805522552356663663333553660667334558916651",
"93333337793311331235542331111442558666112337806539",
"70110005571188118912220229999229226334990115683217",
"70110005571188118912220229999229226334990115683217",
"15554449916633663356665663344663660888445659028761",
"03443338803311431246653452233542558667333338806640",
"92332227782200220134442331111331337556111236795439",
"48998883348866896790008996677997993111778992351094",
"60119994461188018912220119999119115333990114573216",
"69999994460077997901119008899119114223999003462106",
"68999994460077096801108008888008004112888993461096",
"03443338804422552345554553333553559667333448916540",
"70110005571188118912220229999229226334990115683217",
"70110005571188118912220229999229226334990115683217",
"70110005571188118912220229999229226334990115683217"}

{"86336665563355332604443002299076449111996335231408",
"64114443341133110482254880077884227229771883012586",
"38558880015577557152228224411551997996118557489283",
"94114446671133113748854880077887553552774113045849",
"94114446671133113748854880077887553552774113045849",
"94114446671133113748854880077887553552774113045849",
"94114446671133113748854880077887553552774113345819",
"16336668893355335930009002222339772774226338567731",
"72992224459911991593365991188665338007885224190397",
"16336665563355335937776002299009772441996335234731",
"16336665563355335937776002299009772441996335234731",
"83336665560022002937773779966779772118663035231408",
"49669998829988691560032635522365338774229991897064",
"05225554485544554826665221188228994330888527453620",
"83003332263322302604443709966776772118663005231408",
"94117776671133413715554810077887883229774116342519",
"20777776674466776048887443300110116552007449675842",
"08555554452244257126698291188221994663888557456950",
"97447776674433113048884880077110883552777446345849",
"16336665563355335937776002299009772441996335234731",
"16336665563355335937776002299009772441996335234731",
"16336665563355335937776002299009772441996335234731"}

Returns: {"18888888888888881111111888888811111118888888881111", "18888888888888881111188888888881111888881118888811", "11111118881111111118881111111881118888111111188881", "11111118881111111188811111111111118888111111188881", "11111118881111111188811111111111118888111111188881", "11111118881111111188811111111111118888111111188881", "11111118881111111188811111111111118888111111888811", "11111118881111111118888111188881111888881118888111", "11111118881111111111188888888111111111888888811111", "11111111111111111111111111111111111111111111111111", "11111111111111111111111111111111111111111111111111", "11888888881111111888881111111118888111111188881111", "11111111188811188811188811111188888111111888881111", "11111111188811881111111881111881888111118818881111", "11111111188811811111111181111111888111111118881111", "11118888881111811111111181111111888111111118881111", "18881111111111881111111881111111888111111118881111", "18881111111111188811188811111888888888118888888881", "18888888888811111888881111111888888888118888888881", "11111111111111111111111111111111111111111111111111", "11111111111111111111111111111111111111111111111111", "11111111111111111111111111111111111111111111111111" }

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.