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.
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:
-
Initialization: Two matrix data structures
f
andg
of dimensionsn x m
are initialized. Here,n
is the number of players andm
is the bit-length ofk
(which represents the number of powers of 2 required to expressk
in binary form).f[i][j]
will ultimately represent which player has the ball after2^j
passes starting from playeri
, whileg[i][j]
will store the sum of player ids for2^j
passes from playeri
. -
Base Case for DP:
- The zeroth column of
f
, which corresponds to2^0
(or 1 pass), is filled withreceiver[i]
indicating the direct receiver of the ball from each player. - The zeroth column of
g
is filled withi
since the sum of ids after1
pass from the starting playeri
is justi
.
- The zeroth column of
-
DP Recurrence:
- The matrices are filled using a recurrence relation. For a given j-iteration (
j
going from1
tom-1
),f[i][j]
is populated with the player who will receive from the player atf[i][j-1]
after2^(j-1)
passes; thus it's like making a "jump" of2^(j-1)
twice, leading to a total of2^j
passes. - Similarly,
g[i][j]
is the sum of ids for2^j
passes and is calculated as the sum of ids for2^(j-1)
passes from playeri
and from playerf[i][j-1]
.
- The matrices are filled using a recurrence relation. For a given j-iteration (
-
Calculating the Maximum Value of
f(x)
:- The code iterates over each player
i
considering them as the starting player. For each player, it initializesp
as the current player andt
as the total sum of ids. - It then goes through the bits of
k
. If thej
-th bit ofk
is set, it means2^j
passes are part of the totalk
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 idp
is added to the totalt
. This gives the value off(i)
wherei
is the starting player.
- The code iterates over each player
-
Result:
- The maximum value obtained for
t + p
across all starting playersi
is the result of the function and is returned.
- The maximum value obtained for
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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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:
receiver = [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 havef[0][0] = 1
,f[1][0] = 2
,f[2][0] = 3
, andf[3][0] = 0
. - For
g[i][0]
, it is straightforward:g[i][0] = i
, sog[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 setf[i][1]
directly toi
, 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 haveg[i][1] = g[i][0] + g[f[i][0]][0]
, leading tog[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
andp
is the starting player. - For each player
i
as the starting player, examine the bits ofk
, updatingp
and adding tot
accordingly. Fork = 3
, we have two binary digits to consider (11
). - Let's choose player
0
as the starting player. The first bit (rightmost) is1
, so we addg[0][0]
tot
and updatep
tof[0][0]
. Nowt = 0
andp = 1
. - The second bit (next left) is also
1
, so we addg[1][1]
tot
and updatep
tof[1][1]
. Nowt = 3
andp = 3
. - Finally, add player
3
's id tot
: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 player0
gave us6
. If we repeat this for all players, we might find that6
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
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
.
-
Initializing the 2D arrays:
- Initializing two 2D arrays,
f
andg
, of sizen x m
each, wheren
is the length of thereceiver
list andm
is thebit_length()
ofk
. This initialization is done with two list comprehensions that have a complexity ofO(n * m)
.
- Initializing two 2D arrays,
-
Filling the sparse table:
- A nested loop is used where the outer loop runs for
m
iterations (the number of bits ink
) and the inner loop runs forn
iterations (the length of thereceiver
). Thus, the complexity for this part isO(n * m)
.
- A nested loop is used where the outer loop runs for
-
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 ofk
, runs up tom
times. So, in the worst case, this part has a complexity ofO(n * m)
.
- A nested loop where the outer loop runs for
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.
-
Space for 2D arrays:
- Two 2D arrays
f
andg
, each of sizen x m
, give a space complexity ofO(n * m)
.
- Two 2D arrays
-
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.
- Variables
Consequently, the total space complexity is O(n * m)
.
Learn more about how to find time and space complexity quickly using problem constraints.
In a binary min heap, the minimum element can be found in:
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Don’t Miss This!