G. Into Space

The problem in brief

Four magnets must be placed in one plane so that all six pairwise distances are whole numbers. You receive six natural numbers and must answer "yes" if four points in a plane can have exactly these six distances, "no" otherwise. The statement does not say which number is the distance between which pair of magnets, so we treat the assignment as free: the answer is "yes" if some way of attaching the six numbers to the six pairs works. Behind this little puzzle lies a central tool of machine learning: recovering coordinates from distances.

How you are scored

Hidden tests, one line of output, "yes" or "no" (time limit 1 s). We validate our program against an independent geometric construction on all 924 multisets of six numbers between 1 and 7, and on hand-made examples.

First look: what can go wrong?

Three things can prevent a placement:

1. No placement at all, even in space: the distances violate a triangle inequality, like a "triangle" with sides 1, 1, 3.
2. A placement in space only: six equal distances 1 describe a regular tetrahedron, which cannot be flattened.
3. A wrong pairing: the numbers 3, 3, 4, 4, 5, 5 work as a 3 by 4 rectangle with diagonals 5, but if you attach both 5s to opposite sides, they do not.

A natural first idea is to use the Cayley-Menger determinant, which equals $288\,V^2$ where $V$ is the volume of the tetrahedron spanned by the four points: flat means $V = 0$. But it is not enough. The numbers $1, 1, 1, 3, 3, 8$ admit a pairing with zero determinant, yet no placement at all: that pairing contains the impossible triangle 1, 1, 3. A "volume squared" of 0 computed from impossible distances means nothing. We need a test that checks existence and flatness together.

The key idea

Turn distances into dot products. Put magnet 0 at the origin and call $p_1, p_2, p_3$ the positions of the others. Since $\lVert p_i - p_j\rVert^2 = \lVert p_i\rVert^2 + \lVert p_j\rVert^2 - 2\,p_i \cdot p_j$,

$$G_{ij} = p_i \cdot p_j = \frac{d_{0i}^2 + d_{0j}^2 - d_{ij}^2}{2}, \qquad i, j \in \{1, 2, 3\}.$$

$G$ is the Gram matrix of the three vectors, computed from the distances alone. Two facts from linear algebra settle everything:

• Real points with these distances exist if and only if $G$ is positive semidefinite (PSD), because a Gram matrix is always $G = P^\top P$ (so $x^\top G x = \lVert P x\rVert^2 \ge 0$), and conversely a PSD matrix can be factored as $P^\top P$ to recover the points.
• The points fit in a plane if and only if, in addition, $\operatorname{rank} G \le 2$, that is $\det G = 0$ (three vectors in a plane are linearly dependent).

For a symmetric $3 \times 3$ matrix with $\det G = 0$, being PSD is equivalent to all its principal minors being $\ge 0$: the three diagonal entries and the three $2\times 2$ minors $G_{ii}G_{jj} - G_{ij}^2$. Each $2 \times 2$ minor is, up to a factor, Heron's formula for the squared area of a triangle containing magnet 0, so this check is precisely what catches the impossible triangle in $1, 1, 1, 3, 3, 8$: there $G_{11}G_{22} - G_{12}^2 = 1 - 49/4 < 0$.

Everything is an integer if we work with $2G$, so the test is exact: no floating-point tolerance to tune, which matters because a flat configuration sits exactly on the boundary $\det G = 0$.

This "distances to Gram matrix" step is exactly classical multidimensional scaling (MDS): double-centre the squared distances, take the eigenvectors of the resulting Gram matrix, and you get coordinates, with the number of non-zero eigenvalues giving the dimension. It is used to draw maps from distance tables and to visualise embeddings; kernel methods rely on the same PSD condition.

The full solution

PAIRS = [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]

def planar(D):                       # D: pair -> distance
    G = gram2(D)                     # 2 x Gram matrix, integers
    if det3(G) != 0:
        return False                 # needs a third dimension (or nothing works)
    if any(G[k][k] < 0 for k in range(3)):
        return False
    return all(G[i][i] * G[j][j] - G[i][j] ** 2 >= 0
               for i, j in [(0, 1), (0, 2), (1, 2)])

def solve(nums):
    return any(planar(dict(zip(PAIRS, p))) for p in set(itertools.permutations(nums)))

There are at most $6! = 720$ pairings, so trying them all is instant. If your reading of the statement is that the input order is fixed (first number for pair 01, second for 02 and so on), drop the loop and call planar once.

Validation. solution.py --check builds the points with ruler-and-compass geometry in floating point (place 0 and 1 on an axis, intersect circles for 2 and 3, compare the last distance) and compares with the exact test on all 924 multisets of numbers 1 to 7, with zero disagreements. Hand cases: rectangle (yes), rhombus with sides 5 and diagonals 6, 8 (yes), collinear points at 0, 1, 3, 6 (yes: degenerate but planar), regular tetrahedron (no), $1, 1, 1, 3, 3, 8$ (no).

Results

approach	verdict on tricky cases	correct?
Gram matrix PSD + $\det = 0$, exact integers, all pairings	all hand cases and 924 multisets right	yes
Cayley-Menger (or $\det G$) $= 0$ only	says "yes" to $1, 1, 1, 3, 3, 8$	no
same with floats and abs(det) < 1e-9	fragile for large inputs (values up to $10^{18}$)	risky
fixed pairing in input order only	"no" on 3 3 4 4 5 5 if the 5s are not last	depends on the reading
ruler-and-compass construction in floats	right with a tolerance	yes, but needs care

What to remember

• Distances determine dot products: $p_i \cdot p_j = \frac{1}{2}(d_{0i}^2 + d_{0j}^2 - d_{ij}^2)$. This is the heart of classical MDS.
• A matrix of dot products must be positive semidefinite, and its rank is the dimension the points need.
• "Determinant zero" is necessary, not sufficient: always check that the configuration exists at all (PSD, triangle inequalities).
• Prefer exact integer arithmetic when the answer sits on a boundary ($\det = 0$): floating-point tolerances turn yes/no questions into guesses.
• When the statement leaves a mapping unspecified, search over it: 720 permutations cost nothing.