Problem 353: Risky Moon

Mathematical Foundation

Definition. For two points $P_1, P_2$ on a sphere of radius $r$, with unit-sphere projections $\hat{P}_i = P_i / r$, the great-circle arc length is $\theta = \arccos(\hat{P}_1 \cdot \hat{P}_2)$ and the segment risk is

Lemma 1 (Sub-additivity of risk). The risk function $\rho$ satisfies the triangle inequality: for any intermediate point $Q$ on the sphere,

In particular, the minimum-risk path may use fewer hops than the minimum-arc-length path.

Proof. Let $\alpha = \theta(P_1, Q)/2$ and $\beta = \theta(Q, P_2)/2$. Then $\theta(P_1, P_2)/2 \le \alpha + \beta$ by the triangle inequality on the sphere. Since $f(x) = x^2$ is convex, we have $(\alpha + \beta)^2 \le 2(\alpha^2 + \beta^2)$, but this is the wrong direction. However, the key property is that $(\alpha + \beta)^2 \ge \alpha^2 + \beta^2$ for $\alpha, \beta > 0$, which means splitting an arc into sub-arcs strictly reduces total risk. Hence Dijkstra’s algorithm on the complete graph of lattice points finds the true optimum: we want to use as many intermediate hops as possible. $\square$

Theorem 1 (Optimal path structure). For each prime $r$, the minimum-risk path from the north pole $(0,0,r)$ to the south pole $(0,0,-r)$ is the path that minimizes $\sum_i (\theta_i/2)^2$ over all sequences of lattice points connecting the poles. This minimum is found by Dijkstra’s algorithm on the complete graph of lattice points on the sphere of radius $r$, with edge weights $\rho(P_i, P_j)$.

Proof. Since the risk is additive over segments and all pairwise connections are available, the minimum-risk path is the shortest path in the weighted complete graph. Dijkstra’s algorithm finds the shortest path in a graph with non-negative edge weights, which applies here since $\rho \ge 0$. The graph is finite (finitely many lattice points on a sphere of fixed integer radius), so the algorithm terminates. $\square$

Lemma 2 (Lattice point enumeration). The number of integer solutions to $a^2 + b^2 + c^2 = r^2$ is given by the sum-of-three-squares representation function $r_3(r^2)$. For small primes $r \le 14$, this is computable by exhaustive enumeration in $O(r^2)$ time.

Proof. For each value of $c$ with $-r \le c \le r$, we enumerate all pairs $(a,b)$ with $a^2 + b^2 = r^2 - c^2$, which is a sum-of-two-squares problem solvable in $O(r)$ time per value of $c$. Total: $O(r^2)$. $\square$

Editorial

For each prime r <= 14, find lattice points on sphere of radius r, then use Dijkstra to find the minimum-risk path from north pole to south pole. Risk of a segment with arc angle theta = (theta/2)^2. Total answer is the sum over all primes r <= 14. We iterate over r in primes. We then enumerate lattice points on sphere of radius r. Finally, build complete graph with risk weights.

Pseudocode

for r in primes
Enumerate lattice points on sphere of radius r
Build complete graph with risk weights
Dijkstra's algorithm
while Q is not empty

Complexity Analysis

• Time: For each prime $r$, enumerating lattice points takes $O(r^2)$, and Dijkstra on $n = r_3(r^2)$ points takes $O(n^2)$ (dense graph). Since $r \le 13$ and $n$ is at most a few hundred, total time is negligible.
• Space: $O(n^2)$ for the adjacency matrix (or $O(n)$ for Dijkstra with on-the-fly weight computation).

Answer

#include <bits/stdc++.h>
using namespace std;

/*
 * Problem 353: Risky Moon
 *
 * For each prime r <= 14, find all lattice points on the sphere of radius r
 * (i.e., integer (a,b,c) with a^2+b^2+c^2 = r^2).
 * Build a graph and use Dijkstra to find the minimum-risk path from
 * (0,0,r) to (0,0,-r).
 *
 * Risk of a segment with arc angle theta = (theta/2)^2.
 */

int main() {
    vector<int> primes = {2, 3, 5, 7, 11, 13};
    double total_risk = 0.0;

    for (int r : primes) {
        int r2 = r * r;

        // Enumerate all lattice points on sphere of radius r
        vector<tuple<int,int,int>> points;
        for (int a = -r; a <= r; a++) {
            for (int b = -r; b <= r; b++) {
                int rem = r2 - a*a - b*b;
                if (rem < 0) continue;
                int c = (int)round(sqrt((double)rem));
                if (c * c == rem) {
                    points.push_back({a, b, c});
                    if (c > 0) points.push_back({a, b, -c});
                }
            }
        }

        // Remove duplicates
        sort(points.begin(), points.end());
        points.erase(unique(points.begin(), points.end()), points.end());

        int n = points.size();

        // Find north pole (0,0,r) and south pole (0,0,-r)
        int north = -1, south = -1;
        for (int i = 0; i < n; i++) {
            auto [a, b, c] = points[i];
            if (a == 0 && b == 0 && c == r) north = i;
            if (a == 0 && b == 0 && c == -r) south = i;
        }

        if (north == -1 || south == -1) {
            // No lattice points at poles -- skip or handle
            // For r prime: r^2 = 0+0+r^2, so poles always exist
            continue;
        }

        // Dijkstra with all-pairs edges
        vector<double> dist(n, 1e18);
        priority_queue<pair<double,int>, vector<pair<double,int>>, greater<>> pq;
        dist[north] = 0.0;
        pq.push({0.0, north});

        while (!pq.empty()) {
            auto [d, u] = pq.top(); pq.pop();
            if (d > dist[u] + 1e-15) continue;
            if (u == south) break;

            auto [a1, b1, c1] = points[u];
            for (int v = 0; v < n; v++) {
                if (v == u) continue;
                auto [a2, b2, c2] = points[v];
                // cos(theta) = dot / r^2
                double cos_theta = (double)(a1*a2 + b1*b2 + c1*c2) / (double)r2;
                cos_theta = max(-1.0, min(1.0, cos_theta));
                double theta = acos(cos_theta);
                double risk = (theta / 2.0) * (theta / 2.0);
                if (dist[u] + risk < dist[v] - 1e-15) {
                    dist[v] = dist[u] + risk;
                    pq.push({dist[v], v});
                }
            }
        }

        total_risk += dist[south];
    }

    printf("%.10f\n", total_risk);

    return 0;
}

"""
Problem 353: Risky Moon

For each prime r <= 14, find lattice points on sphere of radius r,
then use Dijkstra to find the minimum-risk path from north pole to south pole.

Risk of a segment with arc angle theta = (theta/2)^2.
Total answer is the sum over all primes r <= 14.
"""

import heapq
import math

def solve():
    primes = [2, 3, 5, 7, 11, 13]
    total_risk = 0.0

    for r in primes:
        r2 = r * r

        # Enumerate all lattice points on sphere of radius r
        points = set()
        for a in range(-r, r + 1):
            for b in range(-r, r + 1):
                rem = r2 - a * a - b * b
                if rem < 0:
                    continue
                c = int(round(math.sqrt(rem)))
                if c * c == rem:
                    points.add((a, b, c))
                    if c > 0:
                        points.add((a, b, -c))

        points = list(points)
        n = len(points)
        idx = {p: i for i, p in enumerate(points)}

        north = idx.get((0, 0, r))
        south = idx.get((0, 0, -r))

        if north is None or south is None:
            continue

        # Dijkstra
        dist = [float('inf')] * n
        dist[north] = 0.0
        pq = [(0.0, north)]

        while pq:
            d, u = heapq.heappop(pq)
            if d > dist[u] + 1e-15:
                continue
            if u == south:
                break

            a1, b1, c1 = points[u]
            for v in range(n):
                if v == u:
                    continue
                a2, b2, c2 = points[v]
                cos_theta = (a1 * a2 + b1 * b2 + c1 * c2) / r2
                cos_theta = max(-1.0, min(1.0, cos_theta))
                theta = math.acos(cos_theta)
                risk = (theta / 2.0) ** 2
                if dist[u] + risk < dist[v] - 1e-15:
                    dist[v] = dist[u] + risk
                    heapq.heappush(pq, (dist[v], v))

        total_risk += dist[south]

    print(f"{total_risk:.10f}")

if __name__ == "__main__":
    solve()