Hi everyone, my team participated in ICPC World Finals yesterday and had a lot of fun. However, we noticed that Problem N did not have many solves (only 1 in-contest and none on Kattis), even though our team thought the problem was very fun and doable. Probably, the reason was because numerical algorithms are harder to write in competitive programming languages like C++ and Java.

To help explain the solution better, I made a very concise, annotated Julia notebook that solves the problem in only 16 lines of code. Hopefully you find it conceptually interesting and helpful.

Here is the link to the notebook as a PDF. Alternatively, if you have Julia and Pluto.jl installed, you can run the notebook directly from the source .jl file at this GitHub Gist.

Here's also the Julia code as a standalone program, if you would like to run it on AtCoder or another place. I compressed this program slightly more, so it is only 13 lines of code, including imports and code to read input:

using LinearAlgebra

# Read input
d, n = [parse(Int, x) for x = split(readline())]
n = min(n, d + 1)
data = hcat([[parse(Float64, x) for x = split(readline())] for _ = 1:n]...)
points, dists = data[1:end - 1, :], data[end, :]

# Shift first point to the origin
base, rest = points[:, 1], points[:, 2:end] .- points[:, 1]

# Edge case: n = 1
if n == 1 (base[end] += dists[1]; println(join(base, " ")); exit(0)) end

# Compute linear equation coefficients
A = 2 .* rest'
b = [norm(p)^2 - d^2 + dists[1]^2 for (p, d) = zip(eachcol(rest), dists[2:end])]

# Least-norm solution
Q, R = qr(A')
value = vcat(R' \ b, zeros(d - (n - 1)))

# Shift so that the norm equals dists[1]
value[end] += sqrt(max(0, dists[1]^2 - norm(value)^2))

# Output answer
println(join(Q * value + base, " "))