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](https://gist.github.com/ekzhang/98804315e84f43505630288a7d25530d/raw/5aad4c439d9794b729b732cba936344717649762/vector.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](https://gist.github.com/ekzhang/98804315e84f43505630288a7d25530d).↵
↵
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:↵
↵
<spoiler summary="Julia program">↵
```julia↵
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 = [dot(p, p) - dists[i + 1]^2 + dists[1]^2 for (i, p) = enumerate(eachcol(rest))]↵
↵
# 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, " "))↵
```↵
</spoiler>↵
↵
↵
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](https://gist.github.com/ekzhang/98804315e84f43505630288a7d25530d/raw/5aad4c439d9794b729b732cba936344717649762/vector.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](https://gist.github.com/ekzhang/98804315e84f43505630288a7d25530d).↵
↵
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:↵
↵
<spoiler summary="Julia program">↵
```julia↵
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 = [dot(p, p) - dists[i + 1]^2 + dists[1]^2 for (i, p) = enumerate(eachcol(rest))]↵
↵
# 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, " "))↵
```↵
</spoiler>↵
↵
