Bender - Episode 2 – solution CodinGame en Java
Le bâtiment n'a aucun cycle : c'est un graphe orienté acyclique, et le parcours le plus rentable se calcule par programmation dynamique avec best(r) = argent(r) + max(best(porte1), best(porte2)), une sortie valant 0. On calcule chaque salle une seule fois grâce à la mémoïsation (de façon itérative pour éviter une récursion trop profonde) et on affiche best(0). Le tout est linéaire en O(N).
L'énoncé
Bender entre dans un bâtiment par la salle 0. Chaque salle contient une somme d'argent et possède deux portes, chacune menant soit à une autre salle, soit dehors (notée E). Il ramasse l'argent de chaque salle traversée et veut sortir avec le maximum.
L'entrée donne le nombre de salles (jusqu'à environ 10 000), puis une ligne par salle : son numéro, son montant et ses deux portes. Les salles ne forment jamais de boucle, et il faut afficher un seul entier : le total maximal que Bender peut récolter avant de sortir.
La démarche, étape par étape
- Modéliser le bâtiment comme un grapheChaque salle est un nœud avec au plus deux arcs sortants. Comme l'énoncé garantit qu'aucun parcours ne repasse par une salle, le graphe est un DAG, ce qui transforme le problème du plus long chemin, difficile en général, en un problème facile.
- Écrire la récurrenceSoit best(r) la somme maximale encore récoltable en entrant dans la salle r. Alors best(r) = argent(r) + max(best(a), best(b)) sur ses deux portes, la sortie contribuant 0. Chaque valeur ne dépend que de salles situées plus bas dans le DAG.
- Mémoïser chaque salleDe nombreux parcours atteignent la même salle, donc recalculer best(r) pour chaque parcours explose exponentiellement. On enregistre best(r) à son premier calcul ; chaque salle est alors évaluée exactement une fois.
- Éviter les problèmes de profondeur de récursionUne chaîne de 10 000 salles signifie 10 000 appels imbriqués, ce qui peut faire déborder la pile en Java ou en Python. On utilise une pile explicite (DFS en post-ordre) ou un ordre topologique plutôt qu'une récursion simple.
- Afficher best(0)La réponse est la valeur de la salle d'entrée. Par sécurité, on calcule les sommes sur des entiers 64 bits.
Complexité
O(N)O(N)Chaque salle est empilée et finalisée une seule fois et n'a que deux portes, donc le travail total est linéaire. Des tableaux de taille N contiennent l'argent, les portes et les résultats mémoïsés.
Code de la solution
Bender - Episode 2 – Java
import java.util.*;
import java.io.*;
class Solution {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine().trim());
long[] money = new long[n];
int[][] next = new int[n][2];
for (int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int id = Integer.parseInt(st.nextToken());
money[id] = Long.parseLong(st.nextToken());
for (int k = 0; k < 2; k++) {
String door = st.nextToken();
next[id][k] = door.equals("E") ? -1 : Integer.parseInt(door);
}
}
// best[r] = most money Bender can still collect starting in room r
long[] best = new long[n];
boolean[] done = new boolean[n];
Deque<Integer> stack = new ArrayDeque<>();
stack.push(0);
while (!stack.isEmpty()) {
int r = stack.peek();
if (done[r]) { stack.pop(); continue; }
boolean ready = true;
for (int nx : next[r]) {
if (nx >= 0 && !done[nx]) {
stack.push(nx);
ready = false;
}
}
if (ready) {
long after = 0;
for (int nx : next[r])
if (nx >= 0) after = Math.max(after, best[nx]);
best[r] = money[r] + after;
done[r] = true;
stack.pop();
}
}
System.out.println(best[0]);
}
}
Erreurs fréquentes
- Choisir gloutonnement la porte la plus richePrendre la porte dont la salle suivante contient le plus d'argent échoue dès qu'une salle pauvre mène à une salle riche. Seule la valeur complète best(suivante) dit quelle porte est la meilleure.
- Récursion simple sans mémoExplorer tous les chemins passe les premiers tests et dépasse le temps sur les gros, puisque le nombre de chemins croît exponentiellement avec la profondeur du bâtiment.
- Débordement de pile sur les longues chaînesLes plus gros tests contiennent de longs couloirs de salles. Un DFS récursif descend à 10 000 appels de profondeur, ce qui peut faire planter la pile par défaut de Java et dépasse à coup sûr la limite de récursion par défaut de Python.
- Supposer que les lignes sont dans l'ordreIl faut indexer les tableaux par le numéro de salle écrit sur chaque ligne, pas par la position de la ligne. Cela ne coûte rien et élimine toute une famille de bugs de décalage.
Pour aller plus loin
Pourquoi un DAG rend-il le plus long chemin facile ? Dans un graphe quelconque, le « plus long chemin simple » est NP-difficile parce qu'il faut se souvenir des nœuds déjà visités. Dans un DAG, aucun chemin ne peut revenir sur un nœud, donc l'ensemble des visités n'a plus d'importance et le meilleur parcours depuis une salle ne dépend que de cette salle : c'est exactement la propriété de sous-structure optimale dont la programmation dynamique a besoin. La même astuce fonctionne dans l'autre sens : traiter les salles en ordre topologique et garder, pour chaque salle, le meilleur montant récolté pour l'atteindre (DP vers l'avant). Les deux sont linéaires. Une file qui relâche les nœuds à répétition, comme dans le code d'origine, est un Bellman-Ford déguisé : c'est correct, mais sans ordre topologique le pire cas n'est plus linéaire.
Questions fréquentes
Est-ce un problème de plus court chemin ?
C'est un problème de plus long chemin avec des poids positifs sur les nœuds. Il n'est facile que parce que le bâtiment est acyclique ; Dijkstra ne s'applique pas à une maximisation.
Faut-il un tri topologique ?
Pas explicitement. Un DFS mémoïsé depuis la salle 0 calcule les valeurs dans l'ordre topologique inverse automatiquement, et il ne visite que les salles accessibles depuis l'entrée.
Le total peut-il dépasser un int ?
Les sommes de quelques milliers de salles tiennent en général dans un int 32 bits, mais utiliser un long ne coûte rien et lève tout doute.