2836. Maximize Value of Function in a Ball Passing Game

Problem Link

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

Solution

---

Python3

class Solution:
    def getMaxFunctionValue(self, receiver: List[int], k: int) -> int:
        N = len(receiver)
        M = k.bit_length() + 1
 
        fa = [[0] * M for _ in range(N)]
        scores = [[0] * M for _ in range(N)]
 
        for start, end in enumerate(receiver):
            fa[start][0] = scores[start][0] = end
        
        for p in range(1, M):
            for i in range(N):
                fa[i][p] = fa[fa[i][p - 1]][p - 1]
                scores[i][p] = scores[i][p - 1] + scores[fa[i][p - 1]][p - 1]
        
        res = 0
 
        for i in range(N):
            total = i
 
            for p in range(M):
                if k & (1 << p) > 0:
                    total += scores[i][p]
                    i = fa[i][p]
 
            res = max(res, total)
 
        return res