Coding Solution

Horse-racing Duals – solution CodinGame en C

Facilesortingadjacent differencesgreedyMis à jour le
Réponse courte

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

  1. 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.
  2. 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.
  3. 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().
  4. 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é

TempsO(N log N)
MémoireO(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;
}
            

Erreurs fréquentes

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.

Puzzles similaires

★ 5,0 · 16 avis · 928 utilisateurs Ajouter à Chrome