2836. Maximize Value of Function in a Ball Passing Game
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:
receiver
may 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 <= 105
0 <= receiver[i] <= n - 1
1 <= 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 $2^j$ 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 $2^j$ 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 $2^j$, which is equivalent to passing the ball $2^{j-1}$ times starting from player $i$, and then passing the ball $2^{j-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 \times \log k)$, and the space complexity is $O(n \times \log k)$. Here, $n$ is the number of players.
Similar problems:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
|