AlgoLounge

Maximize Value of Function in a Ball Passing Game

hard

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⁽ᵏ⁾[i].

Return the maximum possible score.

Notes:

  • receiver may contain duplicates.
  • receiver[i] may be equal to i.

Examples

Example 1

Input:  receiver = [2,0,1], k = 4
Output: 6

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

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 <= 10⁵
  • 0 <= receiver[i] <= n - 1
  • 1 <= k <= 10¹⁰
TypeScript
Loading editor…
List of test cases (10)
Case 1
receiver = [2,0,1]
k = 4
Case 2
receiver = [1,1,1,2,3]
k = 3
Case 3
receiver = [0]
k = 1
Case 4
receiver = [0]
k = 10000000000
Case 5
receiver = [0,1,2,3]
k = 10000000000
Case 6
receiver = [1,2,3,3]
k = 5
Case 7
receiver = [1,2,0]
k = 1
Case 8
receiver = [1,2,0]
k = 2
Case 9
receiver = [1,0,3,2,5,4]
k = 7
Case 10
receiver = [0,0,1,2,3,4]
k = 10