Maximize Value of Function in a Ball Passing Game

HARD

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 <= 10⁵
0 <= receiver[i] <= n - 1
1 <= k <= 10¹⁰

Approaches

Checkout 2 different approaches to solve Maximize Value of Function in a Ball Passing Game. Click on different approaches to view the approach and algorithm in detail.

Brute Force Simulation

This approach directly simulates the ball-passing game for each possible starting player. We iterate through all n players, considering each one as a potential starting point. For each starting player, we simulate k passes, accumulating the score along the way by adding the index of each player who touches the ball.

Algorithm

Initialize a variable max_score to 0.
Loop through each player i from 0 to n-1 to consider them as the starting player.
For each starting player i, initialize current_score = i and current_player = i.
Loop k times to simulate the passes:
- Update current_player to receiver[current_player].
- Add the new current_player's index to current_score.
After the inner loop, current_score holds the total score for starting with player i. Update max_score = max(max_score, current_score).
After iterating through all possible starting players, max_score will hold the maximum possible score.

The algorithm iterates through every possible starting player from 0 to n-1. For each start player, it simulates the game for k passes. In each pass, it finds the next player using the receiver array and adds their index to a running total for the current game. This process is repeated k times. The maximum score found across all possible starting players is then returned.

class Solution {
    public long getMaxFunctionValue(int[] receiver, long k) {
        int n = receiver.length;
        long maxScore = 0;

        for (int i = 0; i < n; i++) {
            long currentScore = i;
            int currentPlayer = i;
            for (long j = 0; j < k; j++) {
                currentPlayer = receiver[currentPlayer];
                currentScore += currentPlayer;
            }
            maxScore = Math.max(maxScore, currentScore);
        }
        return maxScore;
    }
}

Complexity Analysis

Time Complexity: O(n * k). The outer loop runs `n` times, and for each iteration, the inner loop runs `k` times. Given `n` up to `10^5` and `k` up to `10^10`, this is computationally infeasible.Space Complexity: O(1), as we only use a few variables to store the current state, not counting the input array.

Pros and Cons

Pros:

Simple to understand and implement.
Requires minimal memory.

Cons:

Extremely inefficient for large values of k.
Will result in a 'Time Limit Exceeded' (TLE) error on most platforms for the given constraints.

Code Solutions

Checking out 3 solutions in different languages for Maximize Value of Function in a Ball Passing Game. Click on different languages to view the code.

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

Video Solution

Watch the video walkthrough for Maximize Value of Function in a Ball Passing Game

Patterns:

Dynamic ProgrammingBit Manipulation

Data Structures:

Array