Coding Solution

Dwarfs standing on the shoulders of giants – solution CodinGame en Python

Moyendirected acyclic graphlongest pathDFS with memoizationMis à jour le
Réponse courte

On construit un graphe orienté où un arc x → y signifie que x a influencé y, puis on calcule le plus long chemin de ce graphe acyclique. Avec un DFS mémoïsé, la longueur de chaîne partant d'une personne vaut 1 plus la plus longue chaîne parmi les personnes qu'elle a influencées (1 si elle n'a influencé personne), et la réponse est le maximum sur toutes les personnes. On compte des personnes, pas des arcs ; le tout est en O(V+E).

L'énoncé

On reçoit n relations (jusqu'à 10 000), chacune étant une paire d'identifiants signifiant que la première personne a influencé la seconde. Les chaînes d'influence ne peuvent pas boucler sur elles-mêmes, mais une personne peut influencer plusieurs autres et être influencée par plusieurs personnes.

Il faut afficher le nombre de personnes dans la plus longue chaîne possible d'influences successives, chaque personne de la chaîne ayant influencé la suivante. Une relation isolée x y donne donc 2.

La démarche, étape par étape

  1. Stocker le graphe en listes d'adjacenceOn associe à chaque identifiant la liste des identifiants qu'il a influencés. Un dictionnaire gère des identifiants épars jusqu'à 10 000 sans allouer un tableau énorme, et les doublons sont sans conséquence.
  2. Définir la longueur de chaîne depuis une personnelongest(v) = 1 si v n'a influencé personne, sinon 1 + max(longest(w)) sur chaque w influencé par v. Comme le graphe n'a pas de cycle, cette récursion termine toujours.
  3. Mémoïser chaque résultatUne personne atteignable depuis de nombreux ancêtres serait sinon recalculée pour chaque chemin, ce qui est exponentiel sur des graphes en losange. Mettre longest(v) en cache fait traiter chaque nœud et chaque arc une seule fois.
  4. Prendre le maximum sur toutes les personnesLes chaînes peuvent partir de n'importe quelle racine et il peut y avoir plusieurs groupes disjoints. On évalue longest(v) pour chaque identifiant (le cache rend cela peu coûteux) et on affiche la plus grande valeur.

Complexité

TempsO(V + E)
MémoireO(V + E)

Avec la mémoïsation, chaque personne est développée une fois et chaque relation suivie une fois. Les listes d'adjacence et le cache sont linéaires en la taille de l'entrée.

Code de la solution

Dwarfs standing on the shoulders of giants – Python

Procède dans l'autre sens : chaque Person conserve sa profondeur depuis l'ancêtre le plus ancien et propage les améliorations vers les personnes qu'elle a influencées à chaque ajout d'arc. C'est correct pour un DAG, mais la propagation peut revisiter des nœuds de nombreuses fois et récurse aussi profondément que la plus longue chaîne : une chaîne de plus d'environ 1000 personnes atteindrait la limite de récursion par défaut de Python.

class Person(object):
    '''Represents a person, which has a unique id, a depth in the tree of relations
       and a list of persons she influenced'''
    def __init__(self, id):
        self.id, self.depth, self.influenced = id, 1, []

    def add(self, p):
        '''add person p amongst the person influenced'''
        self.influenced.append(p)

    def updateDepths(self):
        '''update depths of the persons influenced, according to self depth'''
        for p in self.influenced:
            if (p.depth < self.depth+1):
                p.depth = self.depth+1
                p.updateDepths()

# number of relations
N = int(input())
persons = {}
for i in range(N):
    x, y = [int(j) for j in input().split()]
    if not x in persons:
        persons[x] = Person(x)
    if not y in persons:
        persons[y] = Person(y)
    px, py = persons[x], persons[y]
    px.add(py)
    px.updateDepths()

maximum = 0
for p in persons.values():
    maximum = max(p.depth, maximum)

print(maximum)
            

Erreurs fréquentes

Pour aller plus loin

L'alternative itérative est un tri topologique par l'algorithme de Kahn : on compte les arcs entrants, on place chaque nœud sans arc entrant dans une file avec la profondeur 1, et à chaque nœud dépilé on propose profondeur+1 à ses enfants et on enfile un enfant quand son dernier arc entrant a été traité. La profondeur finale de chaque nœud est la plus longue chaîne qui s'y termine, et le maximum est la réponse. Aucune récursion, un temps en O(V+E), et en bonus la détection d'une entrée invalide : si certains nœuds n'atteignent jamais zéro arc entrant, il y a un cycle et la « plus longue chaîne » serait infinie. C'est le même motif de plus long chemin dans un DAG que celui des problèmes d'ordonnancement, donc il vaut la peine de l'apprendre ici sur une petite entrée.

Questions fréquentes

Pourquoi n'est-ce pas un problème de plus court chemin ou de BFS ?

Un BFS depuis les racines donne la plus courte distance à chaque nœud, alors qu'il faut la plus longue. Dans un DAG, le plus long chemin se calcule facilement par DP sur un ordre topologique, alors que dans un graphe quelconque c'est NP-difficile.

L'entrée peut-elle contenir des cycles ?

Le puzzle garantit que non, puisque personne ne peut influencer sa propre chaîne de mentors. C'est précisément cette garantie qui rend la récursion mémoïsée valide.

Les identifiants commencent-ils à 1 et sont-ils consécutifs ?

Pas forcément ; il faut les traiter comme des étiquettes arbitraires inférieures à 10 000 et utiliser un dictionnaire ou un tableau dimensionné sur l'identifiant maximal.

Puzzles similaires

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