Aggressive Cows

Q: Quelle est la complexité temporelle d’Aggressive Cows ?

Le tri prend O(n log n) et la recherche binaire O(n log D) , où D est l’étendue des emplacements divisée par k-1 . En plus d’une copie triée, la mémoire utilisée est de O(1) .

Q: Pourquoi la première vache va-t-elle toujours dans l'étable la plus à gauche ?

Prenez n’importe quel placement qui fonctionne et déplacez sa vache la plus à gauche vers l’écurie la plus à gauche. Cette vache ne fait que s’éloigner des autres, donc aucune distance ne diminue, et un placement optimal utilise l’écurie la plus à gauche.

Q: Comment repérer une recherche binaire sur la réponse ?

La question demande la plus grande ou la plus petite valeur pour laquelle quelque chose est possible. Vérifier une valeur est beaucoup plus facile que trouver la meilleure, et les réponses ne changent qu’une seule fois à mesure que la valeur augmente. Ici, la valeur est l’écart et la vérification consiste à effectuer le placement glouton.

MoyenRecherche binaire Tri Glouton

+10

Une grange comporte des stalles alignées sur une seule ligne droite, et stalls[i] est la position de la stalle i. Les positions sont toutes différentes et ne suivent aucun ordre particulier. Vous devez placer k vaches dans k stalles différentes, et les vaches se battent lorsqu'elles sont proches les unes des autres ; vous voulez donc que les deux vaches les plus proches soient aussi éloignées que possible.

Retournez la plus grande valeur possible de la distance minimale entre deux vaches quelconques.

Fonction

aggressiveCows(stalls: integer-array, k: integer) → integer

stallsinteger-array: les positions distinctes des stalles, dans n’importe quel ordre
kinteger: le nombre de vaches à placer
Renvoieinteger: la plus grande distance minimale possible entre deux vaches

Contraintes

2 ≤ stalls.length ≤ 5000
0 ≤ stalls[i] ≤ 10⁹
Toutes les positions dans stalls sont distinctes.
2 ≤ k ≤ stalls.length

Exemples

Entrée: stalls = [10, 1, 7, 4, 15]k = 3
Sortie: 6
Explication: Les vaches placées en 1, 7 et 15 sont séparées par 6 puis 8. Une distance de 7 ne convient pas : après 1, la vache suivante est placée en 10, et aucun emplacement ne se trouve en 17 ou au-delà.

Pour aller plus loin

Qu’est-ce qui change si les stands sont disposés en cercle, de sorte que le dernier stand dans l’ordre soit également voisin du premier ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Fixe un écart et demande-toi : est-ce que k vaches peuvent se tenir en étant toutes séparées d’au moins cette distance ? Un passage glouton sur les stalles triées permet de répondre. La réponse passe de oui à non une seule fois à mesure que l’écart augmente, donc la recherche binaire trouve le dernier oui.

Trier, puis essayer chaque intervalle à tour de rôle

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Triez les positions. Les deux vaches les plus proches sont alors toujours voisines, donc un écart g convient lorsque chaque paire de vaches voisines est séparée d’au moins g.

Pour tester un écart, placez une vache dans l’enclos le plus à gauche, puis une autre dans chaque enclos situé à au moins g de la dernière vache. Ce placement glouton permet de placer autant de vaches que n’importe quel autre placement. Alignez n’importe quel placement valide en partant de la gauche : la vache i du placement glouton n’est jamais à droite de la vache i de cet autre placement, donc le placement glouton trouve un enclos pour sa vache suivante au plus tard.

Un écart de 1 convient toujours, alors essayez g = 2, 3, ... et arrêtez-vous au premier écart qui permet de placer moins de k vaches. Dans le premier exemple, un écart de 6 permet de placer 3 vaches et un écart de 7 seulement 2, donc la réponse est 6.

Avec deux vaches et des enclos aux positions 0 et 10^9, cela représente environ 10^9 parcours de 5000 enclos, soit 5 × 10^12 étapes.

Algorithme

Trie les positions.
Écris la vérification pour un écart g : une vache à pos[0], puis une vache dans chaque étable où pos[i] - last ≥ g, en comptant les vaches.
Commence avec gap = 1.
Tant que la vérification pour gap + 1 permet de placer au moins k vaches, ajoute 1 à gap.
Retourne gap.

def cowsPlaced(pos, gap):
    count, last = 1, pos[0]  # the first cow takes the leftmost stall
    for p in pos[1:]:
        if p - last >= gap:
            count += 1
            last = p
    return count


def aggressiveCows(stalls, k):
    pos = sorted(stalls)
    gap = 1  # positions are distinct, so a gap of 1 always fits every cow
    while cowsPlaced(pos, gap + 1) >= k:
        gap += 1
    return gap

Recherche dichotomique sur l’écart

Intuition

Un placement où chaque écart est d’au moins g+1 a également chaque écart d’au moins g, les résultats des tests sont donc oui, ..., oui, non, ..., non. La recherche binaire trouve le dernier oui.

Commencez la recherche avec lo = 1, qui fonctionne toujours, jusqu’à hi = l’étendue divisée par k-1, arrondie à l’entier inférieur : k vaches laissent k-1 écarts dans l’étendue, le plus petit ne peut donc pas être supérieur. Un test réussi définit lo = mid, donc mid doit être arrondi à l’entier supérieur ; arrondis à l’entier inférieur, lo = 5 et hi = 6 se répètent à l’infini.

Dans le premier exemple, l’étendue est de 14 et k = 3, donc hi = 7. Un écart de 4 est accepté, un écart de 6 est accepté, un écart de 7 échoue et l’intervalle se referme sur 6.

Un intervalle d’une largeur allant jusqu’à 10^9 se referme en environ 30 tests portant sur 5000 stalles, soit environ 150 000 étapes.

Algorithme

Trie les positions.
Définis lo = 1 et hi = (pos[n-1] - pos[0]) / (k-1), arrondi à l’entier inférieur.
Tant que lo < hi, prends mid = lo + (hi - lo + 1) / 2.
Si la vérification gloutonne à mid permet de placer au moins k vaches, définis lo = mid ; sinon, définis hi = mid - 1.
Renvoie lo.

def cowsPlaced(pos, gap):
    count, last = 1, pos[0]  # the first cow takes the leftmost stall
    for p in pos[1:]:
        if p - last >= gap:
            count += 1
            last = p
    return count


def aggressiveCows(stalls, k):
    pos = sorted(stalls)
    lo = 1  # positions are distinct, so a gap of 1 always works
    hi = (pos[-1] - pos[0]) // (k - 1)  # k-1 gaps share the whole span
    while lo < hi:
        mid = lo + (hi - lo + 1) // 2  # round up so lo = mid always moves
        if cowsPlaced(pos, mid) >= k:
            lo = mid  # mid fits, so the answer is mid or larger
        else:
            hi = mid - 1  # mid does not fit, so the answer is smaller
    return lo

Pièges et cas limites

Ignorer le tri. Dans la liste non triée [10, 1, 7, 4, 15] avec un écart de 6, la vérification commence à 10, ne trouve aucune étable ultérieure située au moins 6 unités plus loin et indique qu’il y a une vache.
Arrondir mid vers le bas alors qu’une passe définit lo = mid. Une fois que hi = lo + 1, l’intervalle cesse de rétrécir et la boucle ne se termine jamais.
Vérifier qu’il y a exactement k vaches. Avec un écart de 1, le premier exemple place 5 vaches, soit plus que 3, et l’écart convient pourtant ; vérifiez count ≥ k.
Commencer le décompte des vaches à 0. La vache dans l’étable la plus à gauche compte, donc le décompte commence à 1.

Questions fréquentes3

Quelle est la complexité temporelle d’Aggressive Cows ?

Le tri prend O(n log n) et la recherche binaire O(n log D), où D est l’étendue des emplacements divisée par k-1. En plus d’une copie triée, la mémoire utilisée est de O(1).

Pourquoi la première vache va-t-elle toujours dans l'étable la plus à gauche ?

Prenez n’importe quel placement qui fonctionne et déplacez sa vache la plus à gauche vers l’écurie la plus à gauche. Cette vache ne fait que s’éloigner des autres, donc aucune distance ne diminue, et un placement optimal utilise l’écurie la plus à gauche.

Comment repérer une recherche binaire sur la réponse ?

La question demande la plus grande ou la plus petite valeur pour laquelle quelque chose est possible. Vérifier une valeur est beaucoup plus facile que trouver la meilleure, et les réponses ne changent qu’une seule fois à mesure que la valeur augmente. Ici, la valeur est l’écart et la vérification consiste à effectuer le placement glouton.

def aggressiveCows(stalls, k):
    # Écrivez le code ici

Test #1

Test #2

Test #3

Arguments

stalls = [10, 1, 7, 4, 15]
k = 3

Résultat attendu