Bender - Episode 2 – CodinGame solution in Java
The building has no cycles, so it is a directed acyclic graph and the richest route can be computed with dynamic programming: best(r) = money(r) + max(best(door1), best(door2)), where an exit counts as 0. Compute it once per room with memoisation (iteratively, to avoid deep recursion) and print best(0).
The problem
Bender enters a building at room 0. Every room holds some money and has two doors, each leading either to another room or outside (marked E). He picks up the money in each room he walks through and wants to leave with as much as possible.
The input gives the number of rooms (up to about 10,000), then one line per room: its number, its amount of money and its two doors. The rooms never form a loop, and you print a single integer: the maximum total Bender can collect on his way out.
Approach, step by step
- Model the building as a graphEach room is a node with at most two outgoing edges. Because the statement guarantees that no route revisits a room, the graph is a DAG, which turns the usually hard longest-path problem into an easy one.
- Write the recurrenceLet best(r) be the most money you can still collect when entering room r. Then best(r) = money(r) + max(best(a), best(b)) over its two doors, with the exit contributing 0. Every value depends only on rooms further down the DAG.
- Memoise every roomMany routes reach the same room, so recomputing best(r) per route explodes exponentially. Store best(r) the first time it is computed; each room is then evaluated exactly once.
- Avoid recursion depth issuesA chain of 10,000 rooms means 10,000 nested calls, which can overflow the stack in Java or Python. Use an explicit stack (post-order DFS) or a topological order instead of plain recursion.
- Print best(0)The answer is the value of the entrance room. Use a 64-bit integer for the sums to be safe.
Complexity
O(N)O(N)Each room is pushed and finalised once and has only two doors, so the total work is linear. Arrays of size N hold the money, the doors and the memoised results.
Solution code
Bug fixed in this version: The Java block does not compile: Room is a non-static inner class, so `new Room(...)` inside static main fails with 'non-static variable this cannot be referenced from a static context'. Even when Room is made static, the queue-based relaxation re-adds a room every time its value improves, which can be exponential on dense DAGs, and rooms are stored by line order while being looked up by id. The replacement below fixes all three.
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]);
}
}
Common mistakes
- Greedy choice of the richer doorPicking the door whose next room holds more money fails as soon as a poor room leads to a rich one. Only the full value best(next) tells you which door is better.
- Plain recursion without memoExploring every path works on the first tests and times out on the large ones, since the number of paths grows exponentially with the depth of the building.
- Stack overflow on long chainsThe biggest tests contain long corridors of rooms. A recursive DFS goes 10,000 calls deep, which can crash Java's default stack and definitely exceeds Python's default recursion limit.
- Assuming room lines are orderedIndex your arrays by the room number written on each line, not by the line position. It costs nothing and removes a whole class of off-by-one bugs.
Going further
Why does a DAG make longest path easy? In a general graph, 'longest simple path' is NP-hard because you must remember which nodes you already visited. In a DAG, no path can come back to a node, so the visited set is irrelevant and the best route from a room depends only on that room: that is exactly the optimal-substructure property dynamic programming needs. The same trick works the other way round: process rooms in topological order and keep, for each room, the best amount collected to reach it (a forward DP). Both are linear. A queue that re-relaxes nodes, as in the original code, is Bellman-Ford in disguise; it is correct, but without a topological order its worst case is no longer linear.
FAQ
Is this a shortest path problem?
It is a longest path problem with non-negative weights on the nodes. It is only easy because the building is acyclic; Dijkstra does not apply to maximisation.
Do I need a topological sort?
Not explicitly. A memoised DFS from room 0 computes the values in reverse topological order automatically, and it only visits rooms reachable from the entrance.
Can the total overflow an int?
Sums of a few thousand rooms usually fit in a 32-bit int, but using a long costs nothing and removes any doubt.