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:
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 $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:
Python3
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
Java
class Solution {
public long getMaxFunctionValue(List<Integer> receiver, long k) {
int n = receiver.size(), m = 64 - Long.numberOfLeadingZeros(k);
int[][] f = new int[n][m];
long[][] g = new long[n][m];
for (int i = 0; i < n; ++i) {
f[i][0] = receiver.get(i);
g[i][0] = i;
}
for (int j = 1; j < m; ++j) {
for (int i = 0; i < n; ++i) {
f[i][j] = f[f[i][j - 1]][j - 1];
g[i][j] = g[i][j - 1] + g[f[i][j - 1]][j - 1];
}
}
long ans = 0;
for (int i = 0; i < n; ++i) {
int p = i;
long t = 0;
for (int j = 0; j < m; ++j) {
if ((k >> j & 1) == 1) {
t += g[p][j];
p = f[p][j];
}
}
ans = Math.max(ans, p + t);
}
return ans;
}
}
C++
class Solution {
public:
long long getMaxFunctionValue(vector<int>& receiver, long long k) {
int n = receiver.size(), m = 64 - __builtin_clzll(k);
int f[n][m];
long long g[n][m];
for (int i = 0; i < n; ++i) {
f[i][0] = receiver[i];
g[i][0] = i;
}
for (int j = 1; j < m; ++j) {
for (int i = 0; i < n; ++i) {
f[i][j] = f[f[i][j - 1]][j - 1];
g[i][j] = g[i][j - 1] + g[f[i][j - 1]][j - 1];
}
}
long long ans = 0;
for (int i = 0; i < n; ++i) {
int p = i;
long long t = 0;
for (int j = 0; j < m; ++j) {
if (k >> j & 1) {
t += g[p][j];
p = f[p][j];
}
}
ans = max(ans, p + t);
}
return ans;
}
};
Go
func getMaxFunctionValue(receiver []int, k int64) (ans int64) {
n, m := len(receiver), bits.Len(uint(k))
f := make([][]int, n)
g := make([][]int64, n)
for i := range f {
f[i] = make([]int, m)
g[i] = make([]int64, m)
f[i][0] = receiver[i]
g[i][0] = int64(i)
}
for j := 1; j < m; j++ {
for i := 0; i < n; i++ {
f[i][j] = f[f[i][j-1]][j-1]
g[i][j] = g[i][j-1] + g[f[i][j-1]][j-1]
}
}
for i := 0; i < n; i++ {
p := i
t := int64(0)
for j := 0; j < m; j++ {
if k>>j&1 == 1 {
t += g[p][j]
p = f[p][j]
}
}
ans = max(ans, t+int64(p))
}
return
}