Maximize Value of Function in a Ball Passing Game

Maximize Value of Function in a Ball Passing Game

What is this problem about?

You are given an array receiver where receiver[i] is the person who player i passes the ball to. You play a game for k passes. The score of a game starting at player x is the sum of the indices of all players who touch the ball during the k passes (including the starting player). Your goal is to find a starting player that maximizes this total score.

Why is this asked in interviews?

This is a Hard-level Graph problem that tests Binary Lifting (also known as the Successor Graph pattern). Because k can be astronomically large (up to $10^{10}$), simulating the passes step-by-step will immediately Time Limit Exceed. Interviewers ask this to see if you know how to precompute jumps in powers of 2 to traverse massive graphs in $O(\log K)$ time.

Algorithmic pattern used

The definitive pattern is Binary Lifting. Since every node has exactly one outgoing edge, the graph is a "functional graph". We build a 2D table up[node][j], which stores the player who ends up with the ball after $2^j$ passes starting from node. We build a parallel table sum[node][j], which stores the sum of player indices encountered during those $2^j$ passes. To find the score for k passes, we break k down into its binary representation. If the $j$-th bit of k is 1, we add sum[current_node][j] to our total score, and jump our current_node to up[current_node][j].

Example explanation

Players: 0 passes to 1, 1 passes to 2, 2 passes to 0. k = 3. The binary representation of 3 is 11 (which is $2^1 + 2^0$, or 2 passes + 1 pass). If we start at node 1:

• Base score includes starting node: 1.
• We need to make 3 passes.
• Use the $2^0$ (1) pass table: Node 1 passes to 2. We add 2 to score. Current node is now 2.
• Use the $2^1$ (2) pass table: Node 2 after 2 passes goes to (2 -> 0 -> 1). The sum of those 2 passes is $0 + 1 = 1$. Add 1 to score. Current node is 1. Total score for starting at 1 = Base(1) + 2 + 1 = 4. Binary lifting allows us to calculate this using logarithmic steps instead of linear simulation.

Common mistakes candidates make

Candidates frequently try to detect cycles in the graph to optimize the math. While cycle detection works conceptually, implementing cycle extraction, calculating the sum of a full cycle, multiplying by k / cycle_length, and adding the remainder is notoriously bug-prone and messy. Binary Lifting is mathematically much cleaner and easier to write under interview pressure.

Interview preparation tip

If you encounter a graph problem where a single pointer moves millions or billions of steps along directed edges (out-degree = 1), Binary Lifting is the required tool. Practice initializing the up[node][0] base cases, and then building the table using the recurrence: up[node][j] = up[ up[node][j-1] ][j-1]. It's the exact same logic used for finding the Lowest Common Ancestor in $O(\log N)$ time.