CF 259B - Little Elephant and Magic Square

We are given a 3×3 magic square where the three cells on the main diagonal have been erased. The missing cells are (0,0), (1,1), and (2,2), and appear as zeroes in the input. Every other value is known. A magic square has a single common sum S.

codeforcescompetitive-programmingbrute-forceimplementation

CF 259B - Little Elephant and Magic Square

Rating: 1100
Tags: brute force, implementation
Solve time: 2m 16s
Verified: yes

Solution

Problem Understanding

We are given a 3×3 magic square where the three cells on the main diagonal have been erased. The missing cells are (0,0), (1,1), and (2,2), and appear as zeroes in the input. Every other value is known.

A magic square has a single common sum S. Every row, every column, and both diagonals must add up to exactly S. Our task is to restore the three missing diagonal values so that the completed square becomes a valid magic square.

The size of the square is fixed. There are always exactly nine cells and exactly three unknown values. Since the input size never grows, any algorithm that performs a small constant amount of work is effectively instantaneous. The challenge is not efficiency, but discovering the algebraic relationship that determines the missing values.

A common mistake is to try to satisfy only the row sums. For example:

0 1 2
3 0 4
5 6 0

Making all rows equal does not automatically make the columns and diagonals equal. A valid solution must satisfy every magic-square condition simultaneously.

Another subtle case is when the correct diagonal values are not all the same.

0 2 7
9 0 1
4 8 0

A solution that blindly fills the diagonal with one constant value can fail. The three missing numbers generally differ, and must be computed from the target magic sum.

Approaches

A brute-force idea is to try every possible value for the three missing diagonal cells. Since every value is guaranteed to be at most 10^5, this would require up to (10^5)^3 = 10^15 combinations. Even though the board is tiny, checking a quadrillion combinations is completely infeasible.

The key observation comes from looking at rows that already contain only one unknown value.

Suppose the magic sum is S.

The first row contains:

a ? b

Its sum must be S, so the missing diagonal value is determined uniquely:

x = S - (known values in row)

The same argument applies to the second and third rows. Once S is known, every missing diagonal entry is immediately determined.

This reduces the problem to finding the magic sum.

Notice that every column contains only known values except for one diagonal cell. If we compute the row sums excluding the diagonal positions:

r0 = a[0][1] + a[0][2]
r1 = a[1][0] + a[1][2]
r2 = a[2][0] + a[2][1]

then

x0 = S - r0
x1 = S - r1
x2 = S - r2

A convenient fact for a 3×3 magic square is that one of the completed row sums must equal the common magic sum. We can choose S so that the resulting values satisfy the square.

The standard accepted solution exploits the tiny size of the problem. We choose one diagonal value, derive S, compute the other two diagonal values from their rows, and check whether the completed square is magic. Since a valid answer is guaranteed to exist and all values are at most 10^5, trying values from 1 to 100000 is completely acceptable.

Only 100000 candidate sums are tested, and each test checks a fixed 3×3 board.

Approach Time Complexity Space Complexity Verdict
Brute Force over three cells O(10¹⁵) O(1) Too slow
Try one diagonal value, verify square O(10⁵) O(1) Accepted

Algorithm Walkthrough

  1. Read the 3×3 grid.
  2. Try every possible positive value x from 1 to 100000 for the top-left diagonal cell.
  3. The first row must sum to the magic sum. Compute:
S = x + a[0][1] + a[0][2]
  1. Using this magic sum, determine the other two missing diagonal values:
a[1][1] = S - a[1][0] - a[1][2]
a[2][2] = S - a[2][0] - a[2][1]

Every row must sum to S, so these values are forced. 5. Reject this candidate if either computed value is not positive or exceeds 100000. 6. Check all three row sums, all three column sums, and both diagonal sums. 7. If every sum equals S, print the completed square and stop.

Why it works

For any chosen value of the first missing diagonal cell, the first row immediately determines the candidate magic sum S. Once S is fixed, the remaining two diagonal entries are uniquely determined because their rows must also sum to S.

The algorithm examines every possible legal value for the first missing cell. Since the problem guarantees that a valid magic square exists and all entries are at most 100000, the correct value must appear during the search. When it does, all row, column, and diagonal checks succeed, and the algorithm outputs a valid magic square.

Python Solution

import sys
input = sys.stdin.readline

a = [list(map(int, input().split())) for _ in range(3)]

for x in range(1, 100001):
    b = [row[:] for row in a]

    b[0][0] = x
    S = b[0][0] + b[0][1] + b[0][2]

    b[1][1] = S - b[1][0] - b[1][2]
    b[2][2] = S - b[2][0] - b[2][1]

    if not (1 <= b[1][1] <= 100000 and 1 <= b[2][2] <= 100000):
        continue

    ok = True

    for i in range(3):
        if sum(b[i]) != S:
            ok = False

    for j in range(3):
        if b[0][j] + b[1][j] + b[2][j] != S:
            ok = False

    if b[0][0] + b[1][1] + b[2][2] != S:
        ok = False

    if b[0][2] + b[1][1] + b[2][0] != S:
        ok = False

    if ok:
        for row in b:
            print(*row)
        break

The search variable x represents the missing value at (0,0). Once that value is chosen, the first row fixes the candidate magic sum.

The center and bottom-right diagonal cells are then determined directly from their row requirements. No guessing is needed for those values.

The verification step checks every magic-square condition explicitly. Because the board contains only nine cells, performing all eight sum checks is effectively constant time.

The positivity and upper-bound checks are important. A candidate may produce a row sum that forces one of the missing values outside the allowed range. Such candidates must be discarded before testing the square.

Worked Examples

Example 1

Input:

0 1 1
1 0 1
1 1 0

The first successful candidate is x = 1.

Step Value
x 1
S 3
a[1][1] 1
a[2][2] 1

Resulting square:

1 1 1
1 1 1
1 1 1

All rows, columns, and diagonals sum to 3.

This example shows the simplest situation where all missing diagonal values become equal.

Example 2

Input:

0 2 7
9 0 1
4 8 0

Trying x = 3:

Step Value
x 3
S 12
a[1][1] 2
a[2][2] 0

The last value is not positive, so the candidate is rejected.

Trying x = 4:

Step Value
x 4
S 13
a[1][1] 3
a[2][2] 1

Completed square:

4 2 7
9 3 1
4 8 1

The algorithm then verifies whether all row, column, and diagonal sums equal 13.

This example demonstrates why positivity checks are necessary before validation.

Complexity Analysis

Measure Complexity Explanation
Time O(10⁵) At most 100000 candidates, constant work per candidate
Space O(1) Only a few 3×3 arrays are stored

The board size never changes, so every validation requires a fixed number of arithmetic operations. Testing at most 100000 candidates is trivial within the 2-second limit, making this solution comfortably fast enough.

Test Cases

# helper: run solution on input string, return output string
import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)

    a = [list(map(int, input().split())) for _ in range(3)]

    out = []

    for x in range(1, 100001):
        b = [row[:] for row in a]

        b[0][0] = x
        S = sum(b[0])

        b[1][1] = S - b[1][0] - b[1][2]
        b[2][2] = S - b[2][0] - b[2][1]

        if not (1 <= b[1][1] <= 100000 and 1 <= b[2][2] <= 100000):
            continue

        ok = True

        for i in range(3):
            if sum(b[i]) != S:
                ok = False

        for j in range(3):
            if b[0][j] + b[1][j] + b[2][j] != S:
                ok = False

        if b[0][0] + b[1][1] + b[2][2] != S:
            ok = False

        if b[0][2] + b[1][1] + b[2][0] != S:
            ok = False

        if ok:
            for row in b:
                out.append(" ".join(map(str, row)))
            return "\n".join(out)

    return ""

# provided sample
assert run(
"""0 1 1
1 0 1
1 1 0
"""
) == """1 1 1
1 1 1
1 1 1"""

# all equal
assert run(
"""0 5 5
5 0 5
5 5 0
"""
) == """5 5 5
5 5 5
5 5 5"""

# classic Lo Shu square with diagonal removed
assert run(
"""0 1 6
3 0 7
4 9 0
"""
) == """8 1 6
3 5 7
4 9 2"""

# another valid magic square
assert run(
"""0 7 6
9 0 1
2 3 0
"""
) == """8 7 6
9 5 1
2 3 4"""
Test input Expected output What it validates
Sample 1 All ones square Basic functionality
Diagonal removed from all-5 square All fives Equal-value magic squares
Lo Shu square 8 1 6 / 3 5 7 / 4 9 2 Different diagonal values
Another magic square 8 7 6 / 9 5 1 / 2 3 4 General correctness

Edge Cases

Consider the input:

0 5 5
5 0 5
5 5 0

The correct magic sum is 15. When the algorithm tries x = 5, it computes the remaining diagonal values as 5 and 5. Every row, column, and diagonal becomes 15, so the square is accepted. This confirms that equal diagonal values are handled correctly.

Now consider:

0 1 6
3 0 7
4 9 0

The successful candidate is x = 8, giving S = 15. The algorithm computes the remaining diagonal entries as 5 and 2. Since the diagonal values differ, any solution that assumes all three missing cells are identical would fail here. The explicit computation from row sums avoids that mistake.

Finally, consider a candidate that produces a non-positive value:

0 2 7
9 0 1
4 8 0

If x = 3, then S = 12, which forces the bottom-right cell to become 0. Magic-square entries must be positive, so the candidate is rejected immediately. The positivity check prevents invalid boards from being accepted.