Horse-racing Duals – solution CodinGame en C
Lisez les N puissances dans un tableau, triez-le, puis parcourez-le une fois en comparant chaque valeur à la suivante : le plus petit de ces écarts est la réponse. Après le tri, les deux chevaux les plus proches sont forcément voisins, donc inutile de comparer toutes les paires : on passe en O(N log N), largement assez rapide pour 100 000 chevaux.
L'énoncé
On vous donne la puissance de N chevaux, un entier par ligne. Il faut trouver les deux chevaux dont les puissances sont les plus proches et afficher l'écart entre elles.
N peut atteindre 100 000 et les puissances vont jusqu'à 10 000 000. Plusieurs chevaux peuvent avoir la même puissance, auquel cas la réponse est 0. Toute la difficulté est dans la performance : comparer toutes les paires passe sur les petits tests et dépasse le temps sur le gros.
La démarche, étape par étape
- Stocker toutes les puissancesLisez les N valeurs dans un tableau. Impossible de répondre avant la dernière lecture : n'importe quel nouveau cheval peut former une paire plus serrée.
- Trier par ordre croissantUtilisez le tri de la bibliothèque standard (qsort, Arrays.sort, sorted, sort -n). Une fois trié, les valeurs égales ou proches se retrouvent côte à côte.
- Comparer les voisinsCalculez a[i+1] - a[i] pour chaque i et gardez le minimum. L'écart n'est jamais négatif puisque le tableau est trié : pas besoin d'abs().
- Sortir dès un écart nul (optionnel)Si un écart de 0 apparaît, rien ne peut faire mieux : vous pouvez arrêter la boucle et afficher 0 immédiatement.
Complexité
O(N log N)O(N)Le tri domine, le parcours qui suit est linéaire. Garder les N valeurs est indispensable, puisque n'importe quel cheval peut appartenir à la paire la plus proche.
Code de la solution
Horse-racing Duals – C
Lecture dans un tableau de taille variable sur la pile puis tri avec qsort et un comparateur à trois issues ; 100 000 int ne font que 400 Ko, la pile tient.
#include <stdlib.h>
#include <stdio.h>
#include <limits.h>
/* compares the two integers pointed by e1 and e2,
returns -1 / 0 / 1, if e1 < / = / > e2 */
int comp (const void * e1, const void * e2) {
int f = *((int*)e1);
int s = *((int*)e2);
if (f > s) return 1;
if (f < s) return -1;
return 0;
}
int main(int argc, char** argv)
{
int N;
scanf("%d\n", &N);
int horses[N];
for (int i = 0; i < N; i++)
scanf("%d\n", horses+i);
// Sorts the powers
qsort(horses, N, sizeof(int), comp);
int min = INT_MAX;
int diff;
for (int i = 0; i < N-1; i++) {
diff = horses[i+1]-horses[i];
if (diff < min)
min = diff;
}
printf("%d\n", min);
return EXIT_SUCCESS;
}
Horse-racing Duals – Java
import java.util.*;
import java.io.*;
class Solution {
public static void main(String args[]) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(in.readLine().trim());
int[] power = new int[n];
for (int i = 0; i < n; i++)
power[i] = Integer.parseInt(in.readLine().trim());
// after sorting, the closest pair is always made of two neighbours
Arrays.sort(power);
int best = Integer.MAX_VALUE;
for (int i = 1; i < n; i++)
best = Math.min(best, power[i] - power[i - 1]);
System.out.println(best);
}
}
Horse-racing Duals – Python 3
Garde la liste triée pendant la lecture avec bisect.insort, puis compare les voisins. Chaque insertion décale des éléments (O(N²) en théorie), mais ce décalage est un memmove très rapide et le tout tourne en moins d'une seconde pour 100 000 valeurs.
import bisect, sys
N = int(input())
horses = []
mini, diff = sys.maxsize, None
for i in range(N):
bisect.insort(horses, int(input()))
for i in range(N-1):
diff = horses[i+1] - horses[i]
if diff < mini:
mini = diff
print(mini)
Horse-racing Duals – Bash
Fait passer les valeurs dans sort -n pour trier le tableau, puis boucle sur les voisins avec l'expansion arithmétique ; un peu lent mais dans les clous.
#!/bin/bash
read N
# reads all power values and store them in an array
for (( i=0; i<N; i++ ))
do
read p
power[$i]=$p
done
# sorts the array
power=($(for p in ${power[@]}; do echo $p; done | sort -n))
# at this point, power contains all the power sorted by increading order
# the result expected is the smallest difference between 2 consecutive values
min=9999999
for (( i=0; i<${#power[@]}-1; i++ ))
do
current=${power[$i]}
next=${power[$i+1]}
diff=$(( next - current))
if [ $diff -lt $min ]
then
min=$diff
fi
done
echo $min
Erreurs fréquentes
- Double boucle sur toutes les pairesComparer toutes les paires représente environ 5 milliards d'opérations pour N = 100 000. Ça passe les premiers tests et échoue sur le dernier par dépassement de temps.
- Utiliser un ensemble et perdre les doublonsTreeSet, HashSet ou set en Python suppriment les puissances égales, alors que deux chevaux identiques sont justement le cas où la réponse vaut 0. Si vous insérez dans un ensemble, traitez un échec d'insertion comme une réponse immédiate de 0.
- Initialiser le minimum trop basDémarrer le minimum à une valeur arbitraire comme 1 000 000 casse dès que les deux seuls chevaux sont très éloignés. Partez de INT_MAX, de l'infini ou du premier écart.
- Trier comme des chaînesEn JavaScript, sort() sans comparateur trie dans l'ordre lexicographique : 10 passe avant 9. Utilisez sort((a, b) => a - b), et en Bash sort -n plutôt que sort.
- Lecture lente en JavaScanner sur 100 000 lignes est sensiblement lent. Ça passe en général, mais BufferedReader avec Integer.parseInt supprime tout risque.
Pour aller plus loin
Pourquoi comparer seulement les voisins suffit-il ? Dans le tableau trié, prenez une paire non adjacente a[i] < a[j] avec j > i + 1. Alors a[j] - a[i] = (a[j] - a[j-1]) + ... + (a[i+1] - a[i]) : c'est une somme d'écarts adjacents positifs ou nuls, donc au moins aussi grande que chacun d'eux. Le minimum sur toutes les paires est donc toujours atteint par deux voisins. On en déduit aussi que le goulot d'étranglement est le tri, pas le parcours : avec des valeurs bornées par un petit maximum, un tri par comptage ou un tableau de bits donnerait O(N + max). Avec de simples comparaisons, on ne peut pas descendre sous O(N log N) dans le pire cas, car savoir si toutes les valeurs sont distinctes demande déjà ce travail.
Questions fréquentes
Pourquoi ma solution Horse-racing Duals dépasse-t-elle le temps ?
Vous comparez sans doute toutes les paires de chevaux, en O(N²). Triez d'abord et ne comparez que les voisins pour passer en O(N log N).
La réponse peut-elle valoir 0 ?
Oui : si deux chevaux ont la même puissance, l'écart minimal est 0. Les structures qui suppriment les doublons, comme TreeSet ou set, masquent ce cas.
Faut-il abs() pour calculer l'écart ?
Pas après un tri croissant : a[i+1] - a[i] est toujours positif ou nul. abs() n'est utile que si vous comparez les valeurs dans leur ordre d'origine.