Connection Status:
Competition Arena > ReallyMagicSquare

ReallyMagicSquare

SRM 769 · 2019-10-17 · by misof

SRM 769 · 2019-10-17 · by misof · Simple Math
Class Name: ReallyMagicSquare
Return Type: int[]
Method Name: reconstruct
Arg Types: (vector<int>, vector<int>)
Problem Statement

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

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
0)
{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)
{1,7}
{1,4}
Returns: {1, 7, -2, 4 }

The only missing number must be -2, as (-2)+7 = 1+4 = 5.

2)
{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.

3)
{361}
{361}
Returns: {361 }
4)
{441}
{441}
Returns: {441 }

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

Coding Area

Language: C++17 · define a public class ReallyMagicSquare with a public method vector<int> reconstruct(vector<int> topRow, vector<int> mainDiagonal) · 65 test cases · 2 s / 256 MB per case

Submitting as anonymous