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