2836. Maximize Value of Function in a Ball Passing Game


Problem Description

In this problem, you are provided with an array receiver of length n representing a list of n players (each having a unique identifier from 0 to n - 1) participating in a game where they pass a ball to each other. The ball passing is described by receiver[i], which indicates the player that receives the ball from player i. Importantly, a player can pass the ball to themselves.

You are also given an integer k, which is the exact number of times the ball will be passed starting from any chosen player. Your goal is to select a starting player such that the sum of the ids of all players who touch the ball (f(x)), including repetitions and the starting player's id, is maximized after exactly k passes.

To clarify, f(x) is the function that calculates the total mentioned above where x is the starting player's id, and its formula is f(x) = x + receiver[x] + receiver[receiver[x]] + ... until k terms are added up.

Your task is to determine the maximum value that f(x) can reach for any starting player's id x and return this maximum value.

Intuition

The solution involves using dynamic programming to efficiently calculate the sum of ids for each potential starting player, given k passes.

First, we observe that calculating f(x) directly could be costly if k is large, as it would involve following the chain of passes k times. Instead, we can precompute the pass receivers and the id sums for different powers of two, which can be represented in the binary form of k. This allows us to decompose k into a sum of powers of two and compute f(x) using these precomputed values, hence reducing the time complexity.

The idea is to create two matrices f and g, where f[i][j] stores the id of the player who receives the ball from player i after 2^j passes and g[i][j] stores the sum of player ids in 2^j passes from player i. These matrices are filled using dynamic programming.

Once these matrices are precomputed, we iterate over each player i as the starting player. We decompose k into its binary representation and simulate the ball passing to accumulate the sum of ids by checking each bit of k. If the j-th bit of k is set, we update our current player to f[current_player][j] and add the corresponding ids from g[current_player][j] to our total sum.

Utilizing the precomputed values from matrices f and g, we find the accumulated sum of ids t for each possible starting player, and we keep track of the maximum value encountered. The final answer is the largest accumulated sum t plus the last player's id that would be reached with the k passes from each starting player.

The given solution code implements this approach to efficiently compute the desired maximum function value f(x) for a given receiver array and a number of passes k.

Learn more about Dynamic Programming patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

Which data structure is used in a depth first search?

Solution Approach

The implementation of the solution leverages dynamic programming and bit manipulation concepts. Here is a step-by-step breakdown of the approach used in the provided Python code:

  1. Initialization: Two matrix data structures f and g of dimensions n x m are initialized. Here, n is the number of players and m is the bit-length of k (which represents the number of powers of 2 required to express k in binary form). f[i][j] will ultimately represent which player has the ball after 2^j passes starting from player i, while g[i][j] will store the sum of player ids for 2^j passes from player i.

  2. Base Case for DP:

    • The zeroth column of f, which corresponds to 2^0 (or 1 pass), is filled with receiver[i] indicating the direct receiver of the ball from each player.
    • The zeroth column of g is filled with i since the sum of ids after 1 pass from the starting player i is just i.
  3. DP Recurrence:

    • The matrices are filled using a recurrence relation. For a given j-iteration (j going from 1 to m-1), f[i][j] is populated with the player who will receive from the player at f[i][j-1] after 2^(j-1) passes; thus it's like making a "jump" of 2^(j-1) twice, leading to a total of 2^j passes.
    • Similarly, g[i][j] is the sum of ids for 2^j passes and is calculated as the sum of ids for 2^(j-1) passes from player i and from player f[i][j-1].
  4. Calculating the Maximum Value of f(x):

    • The code iterates over each player i considering them as the starting player. For each player, it initializes p as the current player and t as the total sum of ids.
    • It then goes through the bits of k. If the j-th bit of k is set, it means 2^j passes are part of the total k passes. The current player is updated, and the corresponding sum of ids is added to the total.
    • After considering all set bits in k, the final id p is added to the total t. This gives the value of f(i) where i is the starting player.
  5. Result:

    • The maximum value obtained for t + p across all starting players i is the result of the function and is returned.

The dynamic programming aspect of this solution significantly reduces the amount of computation needed by dividing the problem into subproblems that can reuse solutions. It optimizes the process of figuring out the result of k passes by using the binary representation of k and avoids explicit linear chaining of passes.

The recursive relationships in the f and g matrices and bit manipulation for calculating the pass sums are the core components used to derive the solution.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Suppose k is a very large integer(2^64). Which of the following is the largest as n grows to infinity?

Example Walkthrough

Let's illustrate the solution approach with a small example.

Suppose we have the following receiver array representing the players who get the ball next:

1receiver = [1, 2, 3, 0]

This means that player 0 passes the ball to player 1, player 1 passes it to player 2, and so on. If a player would pass the ball back to themselves, it would be indicated by having their own index in their slot (not the case here).

Let's also assume k = 3, meaning the ball will be passed exactly 3 times. Our task is to maximize the sum f(x) of the player ids over these 3 passes.

Step 1: Initialize the matrices f and g. Our matrix will be 4 x 2 since k = 3 (011 in binary, so we need two bits to express it).

Step 2: Fill the base case in both matrices.

  • For f[i][0], we have f[0][0] = 1, f[1][0] = 2, f[2][0] = 3, and f[3][0] = 0.
  • For g[i][0], it is straightforward: g[i][0] = i, so g[0][0] = 0, g[1][0] = 1, etc.

Step 3: Fill the matrices using the dynamic programming approach.

  • We observe that when receiver[i] == receiver[receiver[i]] (which doesn’t happen in this case), we can set f[i][1] directly to i, otherwise use the formula: f[i][1] = receiver[receiver[i]]. So, f[0][1] = f[1][0] = 2, f[1][1] = f[2][0] = 3, etc.
  • For g, we have g[i][1] = g[i][0] + g[f[i][0]][0], leading to g[0][1] = 0 + 1 = 1, g[1][1] = 1 + 2 = 3, etc.

Step 4: Calculate the maximum value of f(x) by iterating over each player as the starting player and considering the bits of k.

  • Initially, t = 0 and p is the starting player.
  • For each player i as the starting player, examine the bits of k, updating p and adding to t accordingly. For k = 3, we have two binary digits to consider (11).
  • Let's choose player 0 as the starting player. The first bit (rightmost) is 1, so we add g[0][0] to t and update p to f[0][0]. Now t = 0 and p = 1.
  • The second bit (next left) is also 1, so we add g[1][1] to t and update p to f[1][1]. Now t = 3 and p = 3.
  • Finally, add player 3's id to t: t = 3 + 3 = 6.
  • We would iterate this process for each player to find the maximum sum.

Step 5: Result

  • The maximum value of t + p that we computed for each starting player is found. In this case, starting with player 0 gave us 6. If we repeat this for all players, we might find that 6 is the maximum or find a higher sum. Let’s say it remains the maximum sum after we went through each player; hence, 6 is our result.

As seen in this small example, the method utilizes dynamic programming to simplify the computation and avoid direct k-pass simulation by instead utilizing a binary representation and matrix table lookups. This makes the solution more efficient, especially for large values of k.

Solution Implementation

1from typing import List
2
3class Solution:
4    def getMaxFunctionValue(self, receiver: List[int], k: int) -> int:
5        num_elements = len(receiver)
6        max_bit_length = k.bit_length()
7      
8        # f[i][j] represents the j-th ancestor of element i after applying the function
9        # g[i][j] represents the sum of elements along the path to the j-th ancestor of i
10        f = [[0] * max_bit_length for _ in range(num_elements)]
11        g = [[0] * max_bit_length for _ in range(num_elements)]
12      
13        # Initialize base ancestors and their sums
14        for index, value in enumerate(receiver):
15            f[index][0] = value
16            g[index][0] = index  # Each element is its own 0-th ancestor
17
18        # Populate the f and g tables for all 2^j-th ancestors
19        for j in range(1, max_bit_length):
20            for i in range(num_elements):
21                # f[i][j] is the 2^(j-1)-th ancestor of f[i][j-1]
22                f[i][j] = f[f[i][j - 1]][j - 1]
23                # g[i][j] is the sum of g[i][j-1] and g of 2^(j-1)-th ancestor of f[i][j-1]
24                g[i][j] = g[i][j - 1] + g[f[i][j - 1]][j - 1]
25
26        max_value = 0
27        # Find the maximum function value for each starting index i
28        for i in range(num_elements):
29            current_position = i
30            total_sum = 0
31          
32            # Use the bits of k to jump to the corresponding ancestors
33            for j in range(max_bit_length):
34                if k >> j & 1:  # If the j-th bit of k is 1, move to the 2^j-th ancestor
35                    total_sum += g[current_position][j]
36                    current_position = f[current_position][j]
37          
38            # Update the maximum value considering the sum and the final position
39            max_value = max(max_value, total_sum + current_position)
40      
41        return max_value
42
43# Example usage:
44# solution = Solution()
45# print(solution.getMaxFunctionValue([2, 0, 1, 5, 3], 3))
46
1class Solution {
2    public long getMaxFunctionValue(List<Integer> receivers, long k) {
3        int numOfReceivers = receivers.size();
4        int maxPowerOfTwo = 64 - Long.numberOfLeadingZeros(k); // Calculate the maximum power of two needed for k
5        int[][] transitions = new int[numOfReceivers][maxPowerOfTwo]; // Transition table for jumping powers of two steps at a time
6        long[][] sums = new long[numOfReceivers][maxPowerOfTwo]; // Table for summation of values after jumps
7
8        // Initialize transitions and sums with direct receivers and their indices.
9        for (int i = 0; i < numOfReceivers; ++i) {
10            transitions[i][0] = receivers.get(i);
11            sums[i][0] = i;
12        }
13
14        // Build the transition and sum tables, where j is the power of two steps we're considering.
15        for (int powerOfTwo = 1; powerOfTwo < maxPowerOfTwo; ++powerOfTwo) {
16            for (int i = 0; i < numOfReceivers; ++i) {
17                transitions[i][powerOfTwo] = transitions[transitions[i][powerOfTwo - 1]][powerOfTwo - 1];
18                sums[i][powerOfTwo] = sums[i][powerOfTwo - 1] + sums[transitions[i][powerOfTwo - 1]][powerOfTwo - 1];
19            }
20        }
21
22        long maxFunctionValue = 0; // Store the maximum function value found.
23
24        // Calculate the function value for each starting receiver
25        for (int i = 0; i < numOfReceivers; ++i) {
26            int currentPosition = i; // Store the current position of the receiver.
27            long currentSum = 0; // Store the current sum of the positions jumped so far.
28
29            // For each power of two, determine if it is a part of the binary representation of k.
30            for (int powerOfTwo = 0; powerOfTwo < maxPowerOfTwo; ++powerOfTwo) {
31                if ((k >> powerOfTwo & 1) == 1) { // Check if the bit at position powerOfTwo is set in k.
32                    currentSum += sums[currentPosition][powerOfTwo];
33                    currentPosition = transitions[currentPosition][powerOfTwo]; // Update the position after the jump.
34                }
35            }
36
37            // Maximize the function by considering the current index and the sum of values due to jumps.
38            maxFunctionValue = Math.max(maxFunctionValue, currentPosition + currentSum);
39        }
40
41        return maxFunctionValue; // Return the maximum function value found.
42    }
43}
44
1#include <vector>
2#include <algorithm>
3using namespace std;
4
5class Solution {
6public:
7    // Function that computes the maximum function value for a given array
8    long long getMaxFunctionValue(vector<int>& receiver, long long k) {
9        int size = receiver.size();
10      
11        // Find the highest bit in 'k' that is set to 1
12        int maxPower = 64 - __builtin_clzll(k);
13      
14        // 'nextReceiver' stores the next receiver in the chain for each power of two
15        int nextReceiver[size][maxPower];
16        // 'cumulativeSum' stores the cumulative sum for each power of two
17        long long cumulativeSum[size][maxPower];
18      
19        // Initialize the base cases (power of 0)
20        for (int i = 0; i < size; ++i) {
21            nextReceiver[i][0] = receiver[i];
22            cumulativeSum[i][0] = i;
23        }
24      
25        // Precompute next receiver and cumulative sums for each power of two
26        for (int power = 1; power < maxPower; ++power) {
27            for (int i = 0; i < size; ++i) {
28                // Find the next receiver by jumping 2^(power-1) steps ahead,
29                // based on the previous power's result
30                nextReceiver[i][power] = nextReceiver[nextReceiver[i][power - 1]][power - 1];
31                // Calculate cumulative sum by adding together the two corresponding 2^(power-1) sums
32                cumulativeSum[i][power] = cumulativeSum[i][power - 1] + cumulativeSum[nextReceiver[i][power - 1]][power - 1];
33            }
34        }
35      
36        long long maxResult = 0;
37        // Iterate over all starting positions
38        for (int i = 0; i < size; ++i) {
39            int currentIndex = i;
40            long long tempSum = 0;
41            // Decompose 'k' into powers of two and calculate the corresponding sums
42            for (int power = 0; power < maxPower; ++power) {
43                // Check if the current bit is set in 'k'
44                if (k & (1LL << power)) {
45                    // Add the sum at the current index and power, and move to the next receiver
46                    tempSum += cumulativeSum[currentIndex][power];
47                    currentIndex = nextReceiver[currentIndex][power];
48                }
49            }
50            // Update the maximum result if the current one is greater
51            maxResult = max(maxResult, currentIndex + tempSum);
52        }
53      
54        return maxResult;
55    }
56};
57
1// Importing necessary utilities from external libraries is not possible in TypeScript
2// but would typically be done using import statements.
3
4// Global variable to store the precomputed next receivers and cumulative sums.
5let nextReceiver: number[][];
6let cumulativeSum: number[][];
7
8// Function that computes the maximum function value for a given array
9function getMaxFunctionValue(receiver: number[], k: bigint): bigint {
10  const size: number = receiver.length;
11
12  // Find the highest bit in 'k' that is set to 1
13  const maxPower: number = 64 - clz(k);
14
15  // Initialize the arrays with the correct dimensions.
16  nextReceiver = Array.from({ length: size }, () => new Array(maxPower));
17  cumulativeSum = Array.from({ length: size }, () => new Array(maxPower));
18
19  // Initialize the base cases (power of 0)
20  for (let i = 0; i < size; ++i) {
21    nextReceiver[i][0] = receiver[i];
22    cumulativeSum[i][0] = i;
23  }
24
25  // Precompute next receiver and cumulative sums for each power of two.
26  for (let power = 1; power < maxPower; ++power) {
27    for (let i = 0; i < size; ++i) {
28      // Find the next receiver by jumping 2^(power-1) steps ahead,
29      // based on the previous power's result.
30      nextReceiver[i][power] =
31        nextReceiver[nextReceiver[i][power - 1]][power - 1];
32      // Calculate cumulative sum by adding together
33      // the two corresponding 2^(power-1) sums.
34      cumulativeSum[i][power] =
35        cumulativeSum[i][power - 1] +
36        cumulativeSum[nextReceiver[i][power - 1]][power - 1];
37    }
38  }
39
40  let maxResult: bigint = BigInt(0);
41
42  // Iterate over all starting positions.
43  for (let i = 0; i < size; ++i) {
44    let currentIndex: number = i;
45    let tempSum: bigint = BigInt(0);
46    // Decompose 'k' into powers of two and calculate the corresponding sums.
47    for (let power = 0; power < maxPower; ++power) {
48      // Check if the current bit is set in 'k'.
49      if (k & BigInt(1) << BigInt(power)) {
50        // Add the sum at the current index and power, and move to the next receiver.
51        tempSum += BigInt(cumulativeSum[currentIndex][power]);
52        currentIndex = nextReceiver[currentIndex][power];
53      }
54    }
55    // Update the maximum result if the current one is greater.
56    maxResult = maxBigInt(maxResult, BigInt(currentIndex) + tempSum);
57  }
58
59  return maxResult;
60}
61
62// Helper function to find the count of leading zeros in a BigInt.
63function clz(value: bigint): number {
64  return value ? 64 - value.toString(2).length : 64;
65}
66
67// Helper function to find the maximum of two BigInts.
68function maxBigInt(a: bigint, b: bigint): bigint {
69  return a > b ? a : b;
70}
71
Not Sure What to Study? Take the 2-min Quiz:

Which of the following is a good use case for backtracking?

Time and Space Complexity

Time Complexity

The time complexity comprises three parts: initializing the 2D arrays f and g, filling in the sparse table f and g, and calculating the maximum function value ans.

  1. Initializing the 2D arrays:

    • Initializing two 2D arrays, f and g, of size n x m each, where n is the length of the receiver list and m is the bit_length() of k. This initialization is done with two list comprehensions that have a complexity of O(n * m).
  2. Filling the sparse table:

    • A nested loop is used where the outer loop runs for m iterations (the number of bits in k) and the inner loop runs for n iterations (the length of the receiver). Thus, the complexity for this part is O(n * m).
  3. Calculating the maximum function value:

    • A nested loop where the outer loop runs for n iterations and the inner loop, conditionally executed based on the bits of k, runs up to m times. So, in the worst case, this part has a complexity of O(n * m).

Summing them all up, the total time complexity is O(n * m + n * m + n * m) = O(n * m).

Space Complexity

The space complexity is determined by the space taken up by the 2D arrays f and g, and by any additional variables used.

  1. Space for 2D arrays:

    • Two 2D arrays f and g, each of size n x m, give a space complexity of O(n * m).
  2. Additional variables:

    • Variables n, m, i, j, p, t, ans, and a few others are used. However, these do not significantly affect the space complexity as their space requirement is constant.

Consequently, the total space complexity is O(n * m).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which algorithm should you use to find a node that is close to the root of the tree?


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫