Editorial for Inaho IV

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Ninjaclasher

The solution requires the knowledge of basic geometry. The question is asking for the Euclidean distance between two points in $N$ $N$ -dimensional space.

First of all, it should be known that the formula for calculating Euclidean distance in $2$ $2$ -dimensional space is:

$\displaystyle d = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}$ $d = \sqrt{(x_{2} - x_{1})^{2} + (y_{2} - y_{1})^{2}}$

For the first subtask, the $2$ $2$ -dimensional distance formula can be expanded to $3$ $3$ dimensions.

$\displaystyle \begin{align*} d &= \sqrt{\left(\sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}\right)^2 + (z_2 - z_1)^2} \\ &= \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2 + (z_2 - z_1)^2} \end{align*}$ $\begin{aligned} d & = \sqrt{{(\sqrt{(x_{2} - x_{1})^{2} + (y_{2} - y_{1})^{2}})}^{2} + (z_{2} - z_{1})^{2}} \\ = \sqrt{(x_{2} - x_{1})^{2} + (y_{2} - y_{1})^{2} + (z_{2} - z_{1})^{2}} \end{aligned}$

For the second and last subtasks, the $2$ $2$ -dimensional distance formula can be expanded to $N$ $N$ -dimensions. The formula for calculating Euclidean distance in $N$ $N$ -dimensional space is

$\displaystyle d = \sqrt{\sum_{i=1}^N (b_i - a_i)^2}$ $d = \sqrt{\sum_{i = 1}^{N} (b_{i} - a_{i})^{2}}$

The proof is left as an exercise for the reader.

The second subtask was specifically dedicated to those who used 32-bit floating-point variables instead of 64-bit floating-point variables in their calculations.

Time Complexity: $\mathcal O(N)$ $O (N)$

Comments

There are no comments at the moment.