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: Binary Lifting + Bit Manipulation

• Time complexity: O(nlogk)
• Space complexity: O(nlogk)

 

JavaScript

/**
 * @param {number[]} receiver
 * @param {number} k
 * @return {number}
 */
const getMaxFunctionValue = function (receiver, k) {
  const m = Math.ceil(Math.log2(k));
  const n = receiver.length;
  const jumps = Array.from({ length: m + 1 }, () => new Array(n).fill(0));
  const sums = Array.from({ length: m + 1 }, () => new Array(n).fill(0));
  let result = 0;

  for (let index = 0; index < n; index++) {
    const value = receiver[index];

    jumps[0][index] = value;
    sums[0][index] = value;
  }

  for (let binary = 1; binary <= m; binary++) {
    for (let index = 0; index < n; index++) {
      const prevPos = jumps[binary - 1][index];
      const prevSum = sums[binary - 1][prevPos];

      jumps[binary][index] = jumps[binary - 1][prevPos];
      sums[binary][index] = sums[binary - 1][index] + prevSum;
    }
  }

  for (let index = 0; index < n; index++) {
    let sum = index;
    let pos = index;
    let binary = 0;
    let binaryK = k;

    while (binaryK) {
      if (binaryK % 2 === 1) {
        sum += sums[binary][pos];
        pos = jumps[binary][pos];
      }

      binaryK = Math.floor(binaryK / 2);
      binary += 1;
    }

    result = Math.max(sum, result);
  }

  return result;
};