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'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; println(join(base, " ")); exit(0)) end # Compute linear equation coefficients A = 2 .* rest' b = [norm(p)^2 - d^2 + dists^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 value[end] += sqrt(max(0, dists^2 - norm(value)^2)) # Output answer println(join(Q * value + base, " "))