ReallyMagicSquare | Topcoder Archive

Problem Statement

An N times N square of integers is called a really magic square if it has the following property: if you pick any N of the N^2 numbers in such a way that no two numbers share the same row and no two numbers share the same column, the sum of the numbers you picked will always be the same.

For example, here is a 4 times 4 square that is really magic:

 140   80  160   60
  90   30  110   10
 100   40  120   20
 130   70  150   50

In the figure below we show two of the twenty-four valid ways to select four numbers such that no two share the same row or column. Note that in both cases the sum is the same: 130 + 80 + 110 + 20 = 130 + 40 + 160 + 10 = 340.

 140  (80) 160   60       140   80 (160)  60
  90   30 (110)  10        90   30  110  (10)
 100   40  120  (20)      100  (40) 120   20
(130)  70  150   50      (130)  70  150   50

You are given the top row of a really magic square in the int[] topRow and its main diagonal in the int[] mainDiagonal. Construct any one really magic square that matches the given numbers. Return a int[] that contains a list of all numbers in your really magic square, read from top to bottom and each row read left to right. If there are multiple solutions, you may return any of them. If there is no solution, return an empty int[].

Definition

Class:: ReallyMagicSquare
Method:: reconstruct
Parameters:: int[], int[]
Returns:: int[]
Method signature:: int[] reconstruct(int[] topRow, int[] mainDiagonal)
(be sure your method is public)

Notes

The main diagonal is the one going from top left to bottom right.
If there is a solution, there is always a solution such that all numbers fit into an int.

Constraints

topRow will contain between 1 and 30 elements, inclusive.
Each element in topRow will be between 1 and 1000, inclusive.
mainDiagonal will contain the same number of elements as topRow.
Each element in mainDiagonal will be between 1 and 1000, inclusive.
topRow[0] will be equal to mainDiagonal[0].

Examples

{140, 80, 160, 60}

{140, 30, 120, 50}

Returns: {140, 80, 160, 60, 90, 30, 110, 10, 100, 40, 120, 20, 130, 70, 150, 50 }

The example from the problem statement.

```
{1,7}
```
```
{1,4}
```
```
Returns: {1, 7, -2, 4 }
```
The only missing number must be -2, as (-2)+7 = 1+4 = 5.

{47,47,47,47,47}

{47,47,47,47,47}

Returns: {47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47 }

A square with all numbers equal is obviously really magic.

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.