Dwarfs standing on the shoulders of giants – CodinGame solution in Python
Build a directed graph where an edge x → y means x influenced y, then compute the longest path in this acyclic graph. With memoized DFS, the chain length starting at a person is 1 plus the longest chain among the people they influenced (1 if they influenced nobody), and the answer is the maximum over all people. Count people, not edges.
The problem
You are given n relations (up to 10,000), each a pair of ids meaning that the first person influenced the second. Influence chains cannot loop back on themselves, but one person can influence several others and be influenced by several people.
Output the number of people in the longest possible chain of successive influences, where each person in the chain influenced the next one. A single isolated relation x y therefore gives 2.
Approach, step by step
- Store the graph as adjacency listsMap each id to the list of ids it influenced. A dictionary handles sparse ids up to 10,000 without allocating a huge array, and duplicates do no harm.
- Define the chain length from a personlongest(v) = 1 if v influenced nobody, otherwise 1 + max(longest(w)) over every w that v influenced. Because the graph has no cycles, this recursion always terminates.
- Memoize each resultA person reachable from many ancestors would otherwise be recomputed for each path, which is exponential on diamond-shaped graphs. Caching longest(v) makes every node and edge processed once.
- Take the maximum over all peopleChains can start at any root and there may be several disconnected groups. Evaluate longest(v) for every id (the cache makes this cheap) and print the largest value.
Complexity
O(V + E)O(V + E)With memoization each person is expanded once and each relation is followed once. The adjacency lists and the cache are linear in the input.
Solution code
Dwarfs standing on the shoulders of giants – Python
Works the other way round: each Person keeps its depth from the oldest ancestor and pushes improvements down to the people it influenced every time an edge is added. It is correct for a DAG, but the propagation can revisit nodes many times and recurses as deep as the longest chain, so a chain of more than about 1000 people would hit Python's default recursion limit.
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)
Common mistakes
- Printing the number of edgesThe longest path in edges is one less than the number of people in it. The single-relation test expects 2, which immediately reveals an off-by-one.
- Assuming the graph is a treeA person can have several mentors, so the structure is a DAG. Plain DFS from every root without caching still gives the right answer but can blow up in time on graphs where many paths share the same subchains.
- Starting only from person 1 or from the first id readThere can be several roots and several independent groups. Either find all nodes with no incoming edge or simply evaluate every node with the cache.
- Recursion depth in PythonA long linear chain makes the recursive DFS as deep as the chain. Raise sys.setrecursionlimit or use an iterative version (topological order, see below) to be safe.
Going further
The iterative alternative is a topological sort with Kahn's algorithm: count incoming edges, put every node with zero incoming edges in a queue with depth 1, and each time you pop a node, offer depth+1 to its children and enqueue a child when its last incoming edge has been processed. The final depth of each node is the longest chain ending at it, and the maximum is the answer. It uses no recursion at all, runs in O(V+E), and as a bonus detects an invalid input: if some nodes never reach zero incoming edges, there is a cycle and the 'longest chain' would be infinite. This is the same longest-path-in-a-DAG pattern you need for scheduling problems, so it is worth learning here on a small input.
FAQ
Why is this not a shortest-path or BFS problem?
BFS from roots gives the shortest distance to each node, but you need the longest one. In a DAG longest path is easy with DP over a topological order, whereas in a general graph it is NP-hard.
Can there be cycles in the input?
The puzzle guarantees there are not, since nobody can influence their own mentor chain. That guarantee is exactly what makes the memoized recursion valid.
Do ids start at 1 and are they consecutive?
Not necessarily; treat them as arbitrary labels under 10,000 and use a dictionary or an array sized to the maximum id.