Description
You are given an integer array receiver of length n and an integer k. n players are playing a ball-passing game.
You choose the starting player, i. The game proceeds as follows: player i passes the ball to player receiver[i], who then passes it to receiver[receiver[i]], and so on, for k passes in total. The game's score is the sum of the indices of the players who touched the ball, including repetitions, i.e. i + receiver[i] + receiver[receiver[i]] + ... + receiver(k)[i].
Return the maximum possible score.
Notes:
receivermay contain duplicates.receiver[i]may be equal toi.
Example 1:
Input: receiver = [2,0,1], k = 4
Output: 6
Explanation:
Starting with player i = 2 the initial score is 2:
| Pass | Sender Index | Receiver Index | Score |
|---|---|---|---|
| 1 | 2 | 1 | 3 |
| 2 | 1 | 0 | 3 |
| 3 | 0 | 2 | 5 |
| 4 | 2 | 1 | 6 |
Example 2:
Input: receiver = [1,1,1,2,3], k = 3
Output: 10
Explanation:
Starting with player i = 4 the initial score is 4:
| Pass | Sender Index | Receiver Index | Score |
|---|---|---|---|
| 1 | 4 | 3 | 7 |
| 2 | 3 | 2 | 9 |
| 3 | 2 | 1 | 10 |
Constraints:
1 <= receiver.length == n <= 1050 <= receiver[i] <= n - 11 <= k <= 1010
Solutions
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.
We can use dynamic programming combined with binary lifting to handle this.
We define f[i][j] as the player ID that can be reached by passing the ball 2j times starting from player i, and define g[i][j] as the sum of the player IDs that can be reached by passing the ball 2j times starting from player i (excluding the last player).
When j=0, the number of passes is 1, so f[i][0] = receiver[i], and g[i][0] = i.
When j > 0, the number of passes is 2j, which is equivalent to passing the ball 2j-1 times starting from player i, and then passing the ball 2j-1 times starting from player f[i][j-1], so f[i][j] = f[f[i][j-1]][j-1], and g[i][j] = g[i][j-1] + g[f[i][j-1]][j-1].
Next, we can enumerate each player i as the starting player, then accumulate upwards according to the binary representation of k, and finally get the maximum sum of the player IDs who have touched the ball within k passes starting from player i.
The time complexity is O(n × log k), and the space complexity is O(n × log k). Here, n is the number of players.
Similar problems:
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(code-box)
