Casablanca’s hippodrome has grown tired of old-fashioned dual racing and has kicked it up a notch: they will now be organizing hyperduals.
During a hyperdual, only two horses will participate in the race. In order for the race to be interesting, it is necessary to try to select two horses with similar strength.
Write a program which, using a given number of strengths, identifies the two closest strengths and shows their difference with an integer.
In a hyperdual, a horse's strength is a bidimensional (Velocity,Elegance)vector. The distance between two strengths (V1,E1) and (V2,E2) is abs(V2-V1)+abs(E2-E1).
(This is a harder version of training puzzle “Horse-racing duals”. You may want to solve that problem first.)
(To date there is no specific achievement if you solve this one in pure bash. Rest assured it *is* possible nonetheless!)
During a hyperdual, only two horses will participate in the race. In order for the race to be interesting, it is necessary to try to select two horses with similar strength.
Write a program which, using a given number of strengths, identifies the two closest strengths and shows their difference with an integer.
In a hyperdual, a horse's strength is a bidimensional (Velocity,Elegance)vector. The distance between two strengths (V1,E1) and (V2,E2) is abs(V2-V1)+abs(E2-E1).
(This is a harder version of training puzzle “Horse-racing duals”. You may want to solve that problem first.)
(To date there is no specific achievement if you solve this one in pure bash. Rest assured it *is* possible nonetheless!)
Input
Line 1: the number N of horses
N following lines: the speed Vi and elegance Ei of each horse, space-separated
N following lines: the speed Vi and elegance Ei of each horse, space-separated
Output
Line 1: the distance D between the two closest strengths
Constraints
10 ≤ N ≤ 600
0 ≤ Vi,Ei ≤ 10000000
D ≥ 0
All values are integral.
0 ≤ Vi,Ei ≤ 10000000
D ≥ 0
All values are integral.
Solution
Instead of sorting and choosing the minimal distance of the pairs, the easiest solution is to choose the minimum distance for each horse to each previously read horse. The number of comparisions is \(0 + 1 + ... + n-1=\frac{1}{2}(n-1)n\in O(n^2)\), but since \(n\leq 600\) this should be okay. Since we read in and compare in one rush, we already solve half of the search space. The worse alternative would be to read in all horses and truly quadratically walk over the array of horse.
const N = +readline();
const horses = [];
let minDist = Infinity;
for (let i = 0; i < N; i++) {
const [Vi, Ei] = readline().split(' ').map(Number);
for (let {Vj, Ej} of horses) {
const dist = Math.abs(Vi - Vj) + Math.abs(Ei - Ej);
minDist = Math.min(minDist, dist);
}
horses.push({Vj: Vi, Ej: Ei});
}
print(minDist); Seeing it differently, we want all combinations of the \(n\) horses, which are \({n\choose 2} = \frac{1}{2}(n-1)n\). So, reading in the horses and generating all 2-combinations would be equivalent to the solution provided.