Codingame Solution: Horse-racing Hyperduals

Original Problem

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!)
Line 1: the number N of horses
N following lines: the speed Vi and elegance Ei of each horse, space-separated
Line 1: the distance D between the two closest strengths
10 ≤ N ≤ 600
0 ≤ Vi,Ei ≤ 10000000
D ≥ 0
All values are integral.


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});

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.

« Back to problem overview