Coding Solution

Network Cabling – solution CodinGame en C

Moyenmediansortinggreedy64-bit integersMis à jour le
Réponse courte

Le câble horizontal doit aller du plus petit au plus grand x, donc sa longueur est fixée à xMax - xMin ; le seul choix est sa hauteur. La somme des descentes verticales |y_i - Y| est minimale quand Y est une médiane des ordonnées des bâtiments : on trie les y, on prend ys[N/2] et on ajoute chaque |y_i - médiane| à xMax - xMin, le tout en entiers 64 bits.

L'énoncé

Un parc d'activités est décrit par les coordonnées entières de N bâtiments. Il faut tous les relier avec un unique câble principal horizontal et, pour chaque bâtiment, un câble vertical qui descend ou monte tout droit du bâtiment jusqu'au câble principal.

On affiche la longueur totale minimale de câble. Il peut y avoir jusqu'à 100 000 bâtiments, les coordonnées vont de -2^30 à 2^30, et le total dépasse la plage 32 bits : la réponse doit être calculée en entiers 64 bits.

La démarche, étape par étape

  1. Séparer les deux dimensionsLe câble principal doit atteindre le bâtiment le plus à gauche et le plus à droite, et un câble plus long n'aide jamais : la partie horizontale vaut toujours xMax - xMin. La hauteur du câble n'influe que sur les parties verticales, donc le problème devient unidimensionnel.
  2. Minimiser la somme des distancesOn cherche la hauteur Y qui minimise la somme des |y_i - Y|. Décaler Y d'une unité change le total de (nombre de bâtiments en dessous) - (nombre au-dessus), donc le total continue de baisser jusqu'à ce que les deux effectifs s'équilibrent, c'est-à-dire exactement à une médiane.
  3. Trouver la médianeOn stocke tous les y, on les trie et on prend ys[N / 2]. Pour N pair, toute valeur entre les deux éléments centraux est optimale, donc l'un ou l'autre convient.
  4. Sommer en 64 bitsOn part de xMax - xMin et on ajoute |y_i - médiane| pour chaque bâtiment, avec des long long en C ou des long en Java. Une seule différence peut déjà valoir 2^31, ce qui ne tient pas dans un int.

Complexité

TempsO(N log N)
MémoireO(N)

Le tri des ordonnées domine. Un algorithme de sélection comme nth_element ou quickselect trouve la médiane en O(N) en moyenne si l'on veut éviter le tri complet.

Code de la solution

Network Cabling – C

#include <stdio.h>
#include <stdlib.h>

static int cmp(const void *a, const void *b) {
    long long x = *(const long long *)a, y = *(const long long *)b;
    return (x > y) - (x < y);
}

int main(void) {
    int n;
    scanf("%d", &n);
    long long *ys = malloc(n * sizeof *ys);
    long long xMin = 0, xMax = 0;
    for (int i = 0; i < n; i++) {
        long long x;
        scanf("%lld %lld", &x, &ys[i]);
        if (i == 0 || x < xMin) xMin = x;
        if (i == 0 || x > xMax) xMax = x;
    }
    qsort(ys, n, sizeof *ys, cmp);
    long long median = ys[n / 2];
    long long total = xMax - xMin;
    for (int i = 0; i < n; i++)
        total += llabs(ys[i] - median);
    printf("%lld\n", total);
    free(ys);
    return 0;
}

Erreurs fréquentes

Pour aller plus loin

L'argument de la médiane mérite d'être compris plutôt que mémorisé, car il explique pourquoi le câble n'a pas à passer par le y d'un bâtiment existant quand N est pair. Triez les y et faites glisser le câble vers le haut d'une unité à la fois : chaque bâtiment au-dessus gagne une unité, chaque bâtiment en dessous en perd une, donc le total s'améliore tant qu'il y a plus de bâtiments au-dessus qu'en dessous. Quand N est pair, les deux effectifs sont égaux pour toute hauteur entre les deux valeurs centrales, donc le coût est plat sur tout ce segment. Cela montre aussi qu'il est inutile de tester des hauteurs candidates ou de lancer une recherche ternaire : le coût est une fonction convexe, linéaire par morceaux, et la médiane en est le minimum. Pour des entrées énormes, nth_element en C++ ou un quickselect trouve la médiane en temps linéaire, mais avec 100 000 bâtiments un simple tri est déjà instantané.

Questions fréquentes

Pourquoi la médiane est-elle optimale dans Network Cabling ?

Monter le câble principal d'une unité raccourcit chaque câble vertical situé au-dessus et allonge chacun de ceux situés en dessous. Le total cesse de s'améliorer seulement quand il y a autant de bâtiments au-dessus qu'en dessous, ce qui est la définition d'une médiane.

Pour un nombre pair de bâtiments, quelle médiane prendre ?

L'une ou l'autre des deux valeurs centrales, ou n'importe quelle hauteur entre elles : le total est identique sur tout cet intervalle, donc ys[N/2] comme ys[N/2 - 1] donnent la bonne réponse.

Pourquoi ma solution échoue-t-elle sur le grand test ?

Presque toujours un débordement d'entier. Utilisez des entiers 64 bits pour les coordonnées, les différences et le total, et vérifiez que votre fonction valeur absolue fonctionne sur 64 bits.

Puzzles similaires

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