#2836

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Maximize Value of Function in a Ball Passing Game

Maximize the total score in a ball-passing game by selecting the best starting player using state transition dynamic programming techniques.

array dynamic programming bit manipulation

Problem Statement

You are given an integer array receiver of length n and an integer k representing n players in a ball-passing game. Each player passes the ball to the player indicated by receiver[i] repeatedly, forming a chain of passes.

Choose a starting player i to begin the game. The total score is the sum of indices of all players who touch the ball in k passes, counting repetitions. Return the maximum possible score achievable after k passes.

Examples

Example 1

Input: receiver = [2,0,1], k = 4

Output: 6

Starting with player i = 2 the initial score is 2:

Example 2

Input: receiver = [1,1,1,2,3], k = 3

Output: 10

Starting with player i = 4 the initial score is 4:

Constraints

1 <= receiver.length == n <= 105
0 <= receiver[i] <= n - 1
1 <= k <= 1010

Solution Approach

Naive Iteration

Simulate each of the k passes from every starting player. Track the cumulative sum of indices at each step. This method fails for large k because its time complexity is O(n*k), which is impractical for k up to 1010.

Binary Lifting Optimization

Precompute jumps using binary lifting. Store 2^j-th receiver indices and cumulative sums for each player. Update positions and total sums in powers of two to handle large k efficiently. This directly implements the state transition dynamic programming pattern needed for this problem.

Selecting Maximum Score

After computing reachable sums with binary lifting, iterate through all starting players and select the one yielding the highest total sum. This ensures you achieve the maximum value for the ball-passing function under the given constraints.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n log k) due to binary lifting jumps across k passes, and space complexity is O(n log k) for storing precomputed jump indices and cumulative sums.

What Interviewers Usually Probe

Expect candidates to immediately consider large k and how naive iteration is too slow.
Look for recognition of repeating patterns in passes and how they enable state transitions.
Signals that candidate knows binary lifting or DP optimizations indicate readiness for hard array-DP problems.

Common Pitfalls or Variants

Common pitfalls

Attempting simple loop simulation results in timeouts for large k.
Overlooking the need to sum indices correctly when cycles occur in the receiver array.
Neglecting space optimization for precomputed jump tables during binary lifting.

Follow-up variants

Return both the maximum score and the starting player achieving it.
Modify the problem to allow different scores for each player instead of their index.
Constrain k to smaller values and compare naive simulation vs DP approach performance.

FAQ

What is the key pattern used in Maximize Value of Function in a Ball Passing Game?

The main pattern is state transition dynamic programming, combined with binary lifting to efficiently compute scores for large k.

Can I use a simple loop to compute the total score?

A simple loop works for small k but is too slow for large k, making binary lifting necessary for efficiency.

What is binary lifting in this context?

Binary lifting precomputes 2^j-th receiver jumps and sums so we can calculate k passes in O(log k) time instead of iterating all passes.

How do I handle cycles in the receiver array?

Use precomputed jump tables and cumulative sums; cycles are automatically handled because each jump considers prior sums up to powers of two.

What are the space and time limits I should watch?

Time complexity is O(n log k) and space complexity is O(n log k), sufficient for n up to 105 and k up to 1010.

terminal

Solution

Solution 1: Dynamic Programming + Binary Lifting

The problem asks us to find the maximum sum of the player IDs who have touched the ball within $k$ passes starting from each player $i$. If we solve it by brute force, we need to traverse upwards $k$ times starting from $i$, with a time complexity of $O(k)$, which will obviously time out.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

class Solution:
    def getMaxFunctionValue(self, receiver: List[int], k: int) -> int:
        n, m = len(receiver), k.bit_length()
        f = [[0] * m for _ in range(n)]
        g = [[0] * m for _ in range(n)]
        for i, x in enumerate(receiver):
            f[i][0] = x
            g[i][0] = i
        for j in range(1, m):
            for i in range(n):
                f[i][j] = f[f[i][j - 1]][j - 1]
                g[i][j] = g[i][j - 1] + g[f[i][j - 1]][j - 1]
        ans = 0
        for i in range(n):
            p, t = i, 0
            for j in range(m):
                if k >> j & 1:
                    t += g[p][j]
                    p = f[p][j]
            ans = max(ans, t + p)
        return ans

Continue Practicing

#2920 maximum points after collecting coins from all nodes #2741 special permutations #2708 maximum strength of a group