A very short solution (<20 lines) to ICPC WF Problem N, in Julia
Разница между en1 и en2, 1,103 символ(ов) изменены
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>↵

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en5 Английский ekzhang 2021-10-07 21:44:07 45
en4 Английский ekzhang 2021-10-07 15:35:35 51 Make b calculation slightly more ergonomic
en3 Английский ekzhang 2021-10-07 15:31:09 6
en2 Английский ekzhang 2021-10-07 15:30:01 1103 Tiny change: 'ram">\n```\nusing Li' -> 'ram">\n```julia\nusing Li'
en1 Английский ekzhang 2021-10-06 15:37:43 1033 Initial revision (published)