A very short solution to Problem N (https://judge.icpc.global/problems/vector) from ICPC Moscow WF in Oct. 2021

vector.jl

### A Pluto.jl notebook ###
# v0.16.1

using Markdown
using InteractiveUtils

# ╔═╡ 4149ed32-773a-48e8-a871-879d36d441f1
using LinearAlgebra

# ╔═╡ 5c627248-2663-11ec-0f78-a773b4888ba6
using Distributions

# ╔═╡ ac8c0662-8a66-42f5-b6ef-824b060ed77e
md"""
# ICPC Moscow WF - Problem N

This is a very short solution (<20 lines of code) with test harness in Julia.

The format of this file is a [Pluto.jl](https://github.com/fonsp/Pluto.jl) notebook, which is a tool for interactive computation. If you change any cell, all cells that depend it will be automatically rerun.
"""

# ╔═╡ 6ab01721-a487-4694-a84a-de742dd232bf
md"""
## Data Generation

First, let's define a helper function that generates random input data according to the random process generating the input. Note that we will additionally assume that $n \leq d + 1$ here.

(In the original problem, you can get this assumption for free by setting $n = \min(n, d + 1)$ at the beginning of the program and ignoring all other input data points.)
"""

# ╔═╡ 40eb816d-6f39-42e1-a2ba-1e027c06f138
dist = Uniform(-100.0, 100.0)

# ╔═╡ bfd83aa6-6b1b-4b83-a7b9-e9dd525de179
function gen_input(d::Int, n::Int)
	points = rand(dist, d, n)
	target = rand(dist, d)
	dists = norm.(eachcol(points .- target))
	points, dists
end

# ╔═╡ bb51a417-8c34-4b84-8f82-1ab27bd81da9
# The largest input from the problem is `gen_input(500, 500)`.
# For this input, the notebook runs in 16 ms on my laptop.
points, dists = gen_input(4, 4)

# ╔═╡ 1312f4c3-4b69-4601-9528-f625ebe85aa9
md"""
## Solving the Problem

Assume that $n \geq 2$, as otherwise, the problem is trivial. Assume without loss of generality that the first point `base = points[0]` is at the origin; we shift all the other points so that this is the case.

If our point is $x \in \mathbb R^d$, the problem reduces to solving the following constraints:

$$\begin{aligned}
  \| x \|^2 &= d_1^2, \\
  \| x - p_i \|^2 &= d_i^2, \quad \text{for } i = 2, 3, \ldots, n.
\end{aligned}$$

Unfortunately, these are quadratic constraints. We can simplify using the identity $\|x-p_i\|^2 = (x-p_i) \cdot (x-p_i) = \|x\|^2 - 2x\cdot p_i + \|p_i\|^2$ to get:

$$\begin{aligned}
  \| x \|^2 &= d_1^2, \\
  2 p_i \cdot x &= \|p\|^2 - d_i^2 + d_1^2, \quad \text{for } i = 2, 3, \ldots, n.
\end{aligned}$$

The latter constraints are simply a linear equation, so we can write them in the form $Ax = b$, for $A \in \mathbb R^{(n - 1) \times d}$ and $b \in \mathbb R^{n-1}$.
"""

# ╔═╡ 2c36c6ed-13d0-4959-aa27-5012fd6acefc
base, rest = points[:, 1], points[:, 2:end] .- points[:, 1]

# ╔═╡ 9d247585-bf43-4a28-b1d1-c9781fcb6b52
A = 2 .* rest'

# ╔═╡ 5f0b1a02-8e8b-4c31-822f-5612a2b7250a
b = [dot(p, p) - dists[i + 1]^2 + dists[1]^2 for (i, p) = enumerate(eachcol(rest))]

# ╔═╡ 1749cf2a-feac-4b3a-b8e8-de4fab87a50c
md"""
To finish the problem, we compute the least-norm solution to $Ax = b$ using QR decomposition. In contest, we implemented this using a simple Gram-Schmidt orthonormalization algorithm in C++.

Since it is the least-norm solution, we are guaranteed to have $\|x\|^2 \leq d_1^2$. Finally, it suffices to find an arbitrary unit vector $o$ in the kernel of $A$ and add $o \sqrt{d_1^2 - \|x\|^2}$ to the least-norm solution $x$.
"""

# ╔═╡ 2883109e-908c-4956-b6ed-cff2267f1966
# A = R'Q'
Q, R = qr(A')

# ╔═╡ a8b93dbb-23c0-4d39-b59b-e5dd2dffb553
# R'Q'x = b
begin
	local value = R' \ b
	while length(value) < size(Q)[1]
		push!(value, 0.0)
	end
	x = Q * value
	if norm(x) < dists[1]
		local o = zeros(length(value))
		o[end] = sqrt(dists[1]^2 - norm(x)^2)
		x = Q * (value + o)
	end
	@assert isapprox(norm(x), dists[1])
	x += base
end

# ╔═╡ 9b63ad91-705a-4695-8ad8-f1313c6c9e3f
md"""
## Validation

Let's check that we solved our input correctly!

You can change the values of $n$ and $d$ in the first cell to verify that this solution still works, as well as to see the runtime of each code block.
"""

# ╔═╡ c1216646-5cf4-4c05-9cc1-d3cd331eca46
# grader: verify conditions
begin
	for (p, d) = zip(eachcol(points), dists)
		@assert isapprox(norm(x - p), d)
	end
	"Tests passed!"
end

# ╔═╡ 00000000-0000-0000-0000-000000000001
PLUTO_PROJECT_TOML_CONTENTS = """
[deps]
Distributions = "31c24e10-a181-5473-b8eb-7969acd0382f"
LinearAlgebra = "37e2e46d-f89d-539d-b4ee-838fcccc9c8e"

[compat]
Distributions = "~0.25.18"
"""

# ╔═╡ 00000000-0000-0000-0000-000000000002
PLUTO_MANIFEST_TOML_CONTENTS = """
# This file is machine-generated - editing it directly is not advised

[[Artifacts]]
deps = ["Pkg"]
git-tree-sha1 = "c30985d8821e0cd73870b17b0ed0ce6dc44cb744"
uuid = "56f22d72-fd6d-98f1-02f0-08ddc0907c33"
version = "1.3.0"

[[Base64]]
uuid = "2a0f44e3-6c83-55bd-87e4-b1978d98bd5f"

[[ChainRulesCore]]
deps = ["Compat", "LinearAlgebra", "SparseArrays"]
git-tree-sha1 = "a325370b9dd0e6bf5656a6f1a7ae80755f8ccc46"
uuid = "d360d2e6-b24c-11e9-a2a3-2a2ae2dbcce4"
version = "1.7.2"

[[Compat]]
deps = ["Base64", "Dates", "DelimitedFiles", "Distributed", "InteractiveUtils", "LibGit2", "Libdl", "LinearAlgebra", "Markdown", "Mmap", "Pkg", "Printf", "REPL", "Random", "SHA", "Serialization", "SharedArrays", "Sockets", "SparseArrays", "Statistics", "Test", "UUIDs", "Unicode"]
git-tree-sha1 = "31d0151f5716b655421d9d75b7fa74cc4e744df2"
uuid = "34da2185-b29b-5c13-b0c7-acf172513d20"
version = "3.39.0"

[[CompilerSupportLibraries_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg"]
git-tree-sha1 = "8e695f735fca77e9708e795eda62afdb869cbb70"
uuid = "e66e0078-7015-5450-92f7-15fbd957f2ae"
version = "0.3.4+0"

[[DataAPI]]
git-tree-sha1 = "cc70b17275652eb47bc9e5f81635981f13cea5c8"
uuid = "9a962f9c-6df0-11e9-0e5d-c546b8b5ee8a"
version = "1.9.0"

[[DataStructures]]
deps = ["Compat", "InteractiveUtils", "OrderedCollections"]
git-tree-sha1 = "7d9d316f04214f7efdbb6398d545446e246eff02"
uuid = "864edb3b-99cc-5e75-8d2d-829cb0a9cfe8"
version = "0.18.10"

[[Dates]]
deps = ["Printf"]
uuid = "ade2ca70-3891-5945-98fb-dc099432e06a"

[[DelimitedFiles]]
deps = ["Mmap"]
uuid = "8bb1440f-4735-579b-a4ab-409b98df4dab"

[[Distributed]]
deps = ["Random", "Serialization", "Sockets"]
uuid = "8ba89e20-285c-5b6f-9357-94700520ee1b"

[[Distributions]]
deps = ["ChainRulesCore", "FillArrays", "LinearAlgebra", "PDMats", "Printf", "QuadGK", "Random", "SparseArrays", "SpecialFunctions", "Statistics", "StatsBase", "StatsFuns"]
git-tree-sha1 = "ff7890c74e2eaffbc0b3741811e3816e64b6343d"
uuid = "31c24e10-a181-5473-b8eb-7969acd0382f"
version = "0.25.18"

[[DocStringExtensions]]
deps = ["LibGit2"]
git-tree-sha1 = "a32185f5428d3986f47c2ab78b1f216d5e6cc96f"
uuid = "ffbed154-4ef7-542d-bbb7-c09d3a79fcae"
version = "0.8.5"

[[FillArrays]]
deps = ["LinearAlgebra", "Random", "SparseArrays", "Statistics"]
git-tree-sha1 = "29890dfbc427afa59598b8cfcc10034719bd7744"
uuid = "1a297f60-69ca-5386-bcde-b61e274b549b"
version = "0.12.6"

[[InteractiveUtils]]
deps = ["Markdown"]
uuid = "b77e0a4c-d291-57a0-90e8-8db25a27a240"

[[IrrationalConstants]]
git-tree-sha1 = "f76424439413893a832026ca355fe273e93bce94"
uuid = "92d709cd-6900-40b7-9082-c6be49f344b6"
version = "0.1.0"

[[JLLWrappers]]
deps = ["Preferences"]
git-tree-sha1 = "642a199af8b68253517b80bd3bfd17eb4e84df6e"
uuid = "692b3bcd-3c85-4b1f-b108-f13ce0eb3210"
version = "1.3.0"

[[LibGit2]]
deps = ["Printf"]
uuid = "76f85450-5226-5b5a-8eaa-529ad045b433"

[[Libdl]]
uuid = "8f399da3-3557-5675-b5ff-fb832c97cbdb"

[[LinearAlgebra]]
deps = ["Libdl"]
uuid = "37e2e46d-f89d-539d-b4ee-838fcccc9c8e"

[[LogExpFunctions]]
deps = ["ChainRulesCore", "DocStringExtensions", "IrrationalConstants", "LinearAlgebra"]
git-tree-sha1 = "34dc30f868e368f8a17b728a1238f3fcda43931a"
uuid = "2ab3a3ac-af41-5b50-aa03-7779005ae688"
version = "0.3.3"

[[Logging]]
uuid = "56ddb016-857b-54e1-b83d-db4d58db5568"

[[Markdown]]
deps = ["Base64"]
uuid = "d6f4376e-aef5-505a-96c1-9c027394607a"

[[Missings]]
deps = ["DataAPI"]
git-tree-sha1 = "bf210ce90b6c9eed32d25dbcae1ebc565df2687f"
uuid = "e1d29d7a-bbdc-5cf2-9ac0-f12de2c33e28"
version = "1.0.2"

[[Mmap]]
uuid = "a63ad114-7e13-5084-954f-fe012c677804"

[[OpenLibm_jll]]
deps = ["Libdl", "Pkg"]
git-tree-sha1 = "d22054f66695fe580009c09e765175cbf7f13031"
uuid = "05823500-19ac-5b8b-9628-191a04bc5112"
version = "0.7.1+0"

[[OpenSpecFun_jll]]
deps = ["Artifacts", "CompilerSupportLibraries_jll", "JLLWrappers", "Libdl", "Pkg"]
git-tree-sha1 = "9db77584158d0ab52307f8c04f8e7c08ca76b5b3"
uuid = "efe28fd5-8261-553b-a9e1-b2916fc3738e"
version = "0.5.3+4"

[[OrderedCollections]]
git-tree-sha1 = "85f8e6578bf1f9ee0d11e7bb1b1456435479d47c"
uuid = "bac558e1-5e72-5ebc-8fee-abe8a469f55d"
version = "1.4.1"

[[PDMats]]
deps = ["LinearAlgebra", "SparseArrays", "SuiteSparse"]
git-tree-sha1 = "4dd403333bcf0909341cfe57ec115152f937d7d8"
uuid = "90014a1f-27ba-587c-ab20-58faa44d9150"
version = "0.11.1"

[[Pkg]]
deps = ["Dates", "LibGit2", "Libdl", "Logging", "Markdown", "Printf", "REPL", "Random", "SHA", "UUIDs"]
uuid = "44cfe95a-1eb2-52ea-b672-e2afdf69b78f"

[[Preferences]]
deps = ["TOML"]
git-tree-sha1 = "00cfd92944ca9c760982747e9a1d0d5d86ab1e5a"
uuid = "21216c6a-2e73-6563-6e65-726566657250"
version = "1.2.2"

[[Printf]]
deps = ["Unicode"]
uuid = "de0858da-6303-5e67-8744-51eddeeeb8d7"

[[QuadGK]]
deps = ["DataStructures", "LinearAlgebra"]
git-tree-sha1 = "78aadffb3efd2155af139781b8a8df1ef279ea39"
uuid = "1fd47b50-473d-5c70-9696-f719f8f3bcdc"
version = "2.4.2"

[[REPL]]
deps = ["InteractiveUtils", "Markdown", "Sockets"]
uuid = "3fa0cd96-eef1-5676-8a61-b3b8758bbffb"

[[Random]]
deps = ["Serialization"]
uuid = "9a3f8284-a2c9-5f02-9a11-845980a1fd5c"

[[Reexport]]
git-tree-sha1 = "45e428421666073eab6f2da5c9d310d99bb12f9b"
uuid = "189a3867-3050-52da-a836-e630ba90ab69"
version = "1.2.2"

[[Rmath]]
deps = ["Random", "Rmath_jll"]
git-tree-sha1 = "86c5647b565873641538d8f812c04e4c9dbeb370"
uuid = "79098fc4-a85e-5d69-aa6a-4863f24498fa"
version = "0.6.1"

[[Rmath_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg"]
git-tree-sha1 = "1b7bf41258f6c5c9c31df8c1ba34c1fc88674957"
uuid = "f50d1b31-88e8-58de-be2c-1cc44531875f"
version = "0.2.2+2"

[[SHA]]
uuid = "ea8e919c-243c-51af-8825-aaa63cd721ce"

[[Serialization]]
uuid = "9e88b42a-f829-5b0c-bbe9-9e923198166b"

[[SharedArrays]]
deps = ["Distributed", "Mmap", "Random", "Serialization"]
uuid = "1a1011a3-84de-559e-8e89-a11a2f7dc383"

[[Sockets]]
uuid = "6462fe0b-24de-5631-8697-dd941f90decc"

[[SortingAlgorithms]]
deps = ["DataStructures"]
git-tree-sha1 = "b3363d7460f7d098ca0912c69b082f75625d7508"
uuid = "a2af1166-a08f-5f64-846c-94a0d3cef48c"
version = "1.0.1"

[[SparseArrays]]
deps = ["LinearAlgebra", "Random"]
uuid = "2f01184e-e22b-5df5-ae63-d93ebab69eaf"

[[SpecialFunctions]]
deps = ["ChainRulesCore", "IrrationalConstants", "LogExpFunctions", "OpenLibm_jll", "OpenSpecFun_jll"]
git-tree-sha1 = "793793f1df98e3d7d554b65a107e9c9a6399a6ed"
uuid = "276daf66-3868-5448-9aa4-cd146d93841b"
version = "1.7.0"

[[Statistics]]
deps = ["LinearAlgebra", "SparseArrays"]
uuid = "10745b16-79ce-11e8-11f9-7d13ad32a3b2"

[[StatsAPI]]
git-tree-sha1 = "1958272568dc176a1d881acb797beb909c785510"
uuid = "82ae8749-77ed-4fe6-ae5f-f523153014b0"
version = "1.0.0"

[[StatsBase]]
deps = ["DataAPI", "DataStructures", "LinearAlgebra", "Missings", "Printf", "Random", "SortingAlgorithms", "SparseArrays", "Statistics", "StatsAPI"]
git-tree-sha1 = "8cbbc098554648c84f79a463c9ff0fd277144b6c"
uuid = "2913bbd2-ae8a-5f71-8c99-4fb6c76f3a91"
version = "0.33.10"

[[StatsFuns]]
deps = ["ChainRulesCore", "IrrationalConstants", "LogExpFunctions", "Reexport", "Rmath", "SpecialFunctions"]
git-tree-sha1 = "95072ef1a22b057b1e80f73c2a89ad238ae4cfff"
uuid = "4c63d2b9-4356-54db-8cca-17b64c39e42c"
version = "0.9.12"

[[SuiteSparse]]
deps = ["Libdl", "LinearAlgebra", "Serialization", "SparseArrays"]
uuid = "4607b0f0-06f3-5cda-b6b1-a6196a1729e9"

[[TOML]]
deps = ["Dates"]
git-tree-sha1 = "44aaac2d2aec4a850302f9aa69127c74f0c3787e"
uuid = "fa267f1f-6049-4f14-aa54-33bafae1ed76"
version = "1.0.3"

[[Test]]
deps = ["Distributed", "InteractiveUtils", "Logging", "Random"]
uuid = "8dfed614-e22c-5e08-85e1-65c5234f0b40"

[[UUIDs]]
deps = ["Random", "SHA"]
uuid = "cf7118a7-6976-5b1a-9a39-7adc72f591a4"

[[Unicode]]
uuid = "4ec0a83e-493e-50e2-b9ac-8f72acf5a8f5"
"""

# ╔═╡ Cell order:
# ╟─ac8c0662-8a66-42f5-b6ef-824b060ed77e
# ╠═4149ed32-773a-48e8-a871-879d36d441f1
# ╠═5c627248-2663-11ec-0f78-a773b4888ba6
# ╟─6ab01721-a487-4694-a84a-de742dd232bf
# ╠═40eb816d-6f39-42e1-a2ba-1e027c06f138
# ╠═bfd83aa6-6b1b-4b83-a7b9-e9dd525de179
# ╠═bb51a417-8c34-4b84-8f82-1ab27bd81da9
# ╟─1312f4c3-4b69-4601-9528-f625ebe85aa9
# ╠═2c36c6ed-13d0-4959-aa27-5012fd6acefc
# ╠═9d247585-bf43-4a28-b1d1-c9781fcb6b52
# ╠═5f0b1a02-8e8b-4c31-822f-5612a2b7250a
# ╟─1749cf2a-feac-4b3a-b8e8-de4fab87a50c
# ╠═2883109e-908c-4956-b6ed-cff2267f1966
# ╠═a8b93dbb-23c0-4d39-b59b-e5dd2dffb553
# ╟─9b63ad91-705a-4695-8ad8-f1313c6c9e3f
# ╠═c1216646-5cf4-4c05-9cc1-d3cd331eca46
# ╟─00000000-0000-0000-0000-000000000001
# ╟─00000000-0000-0000-0000-000000000002

vector.pdf

vector1.jl

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, " "))