Connection Status:
Competition Arena > MagicCube
SRM 256 · 2005-08-02 · by lars2520 · Simple Math
Class Name: MagicCube
Return Type: int
Method Name: getScore
Arg Types: (vector<int>)
Problem Statement

Problem Statement

We've all seen magic squares before. They are square grids full of numbers arranged so that the rows, columns and diagonals all have the same sum:
 8 1 6
 3 5 7
 4 9 2
In the above figure, each row, column and diagonal sums to 15.

We'd like to extend the magic square to the magic cube. In a magic cube, we'll ignore the diagonals, but would like the rows, columns and pillars (pillars are analogous to rows and columns, but in the third dimension) to all have the same sum. You will be given 27 numbers that form the 27 values in a 3x3x3 cube. The number at (i,j,k) in the cube will be represented by element i*9 + j*3 + k of the input.

We can define the 'magic score' of a cube as the difference between the largest sum and the smallest sum (where the sums come from rows, columns, and pillars). Your task is to try to make the cube slightly more magical by trying to decrease its magic score. You should try to find two numbers in the cube that can be swapped to lower the cube's magic score. You should return the minimum possible magic score of the cube after you perform one swap. If there is no swap that would lower the magic score, return the magic score without any swaps.

Constraints

  • nums will contain exactly 27 elements, each between 1 and 100, inclusive.
Examples
0)
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}
Returns: 0
1)
{23,4,10,1,27,21,25,7,17,9,15,13,20,3,11,2,22,18,12,24,14,26,8,6,5,19,16}
Returns: 18

In the original cube, the magic score is 51-31=20. By swapping the numbers at (0,0,1) and (1,2,0), we can improve the magic score to 51-33=18

2)
{23,2,10,1,27,21,25,7,17,9,15,13,20,3,11,4,22,18,12,24,14,26,8,6,5,19,16}
Returns: 17
3)
{23,2,9,1,27,21,25,7,17,10,15,13,20,3,11,4,22,18,12,24,14,26,8,6,5,19,16}
Returns: 17
4)
{24,2,3,5,20,15,14,8,19,6,23,21,25,1,13,17,26,18,27,11,9,16,12,4,7,10,22}
Returns: 25

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

Coding Area

Language: C++17 · define a public class MagicCube with a public method int getScore(vector<int> nums) · 23 test cases · 2 s / 256 MB per case

Submitting as anonymous