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 to i.

 

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:

• 1483. Kth Ancestor of a Tree Node

Python3JavaC++Go

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

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;
    }
}

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;
    }
};

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
}

Comments