# Maximize Value of Function in a Ball Passing Game
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximize-value-of-function-in-a-ball-passing-game)
Canonical: https://scaleengineer.com/dsa/problems/maximize-value-of-function-in-a-ball-passing-game
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Data structures:** Array
---
## Problem
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`

# Approaches
## 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.
**Time:** 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:** O(1), as we only use a few variables to store the current state, not counting the input array.
**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.
### Explanation
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.

```java
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;
    }
}
```
### 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.

## Binary Lifting for Path Queries
The brute-force approach is too slow because `k` can be very large. We can optimize this by precomputing information about paths of lengths that are powers of two. This technique is known as binary lifting or sparse table. The core idea is to break down the long path of `k` passes into segments whose lengths are powers of two. After an `O(n log k)` precomputation, we can find the destination and the sum of any path of length `k` in `O(log k)` time.
**Time:** O(n * log k). The precomputation takes `O(n * log k)`. The query part iterates through `n` starting nodes, and each query takes `O(log k)`. The total time is dominated by these two parts. · **Space:** O(n * log k). We use two 2D arrays of size `n x m`, where `m` is approximately `log2(k)`.
**Pros:** Highly efficient for large `k`, making it feasible for the given constraints.; It's a standard and powerful technique for path-related problems on functional graphs or trees.
**Cons:** Uses significantly more memory, O(n * log k), compared to the brute-force approach.; The implementation is more complex and less intuitive than a direct simulation.
### Explanation
We use dynamic programming to precompute jumps of powers of two. We create two tables:
- `nextPlayer[i][j]`: stores the player you reach after `2^j` passes starting from player `i`.
- `pathSum[i][j]`: stores the sum of player indices on a path of `2^j` nodes, starting from player `i`.

The recurrence relations are:
- `nextPlayer[i][j] = nextPlayer[nextPlayer[i][j-1]][j-1]` (A jump of `2^j` is two jumps of `2^(j-1)`).
- `pathSum[i][j] = pathSum[i][j-1] + pathSum[nextPlayer[i][j-1]][j-1]` (The sum for a `2^j` path is the sum of the first `2^(j-1)` path segment plus the sum of the next `2^(j-1)` path segment).

After precomputing these tables, we can answer the query for any starting player `i` and any number of passes `k`. The total score is the sum of indices of `k+1` players. We find this sum by decomposing `k+1` into its binary representation and summing up the precomputed `pathSum` values for the corresponding powers of two.

```java
class Solution {
    public long getMaxFunctionValue(int[] receiver, long k) {
        int n = receiver.length;
        // The number of bits needed to represent k. Add 1 for safety.
        int m = (int) (Math.log(k) / Math.log(2)) + 2;

        // nextPlayer[i][j]: player after 2^j steps starting from i
        int[][] nextPlayer = new int[n][m];
        // pathSum[i][j]: sum of path of length 2^j starting from i
        long[][] pathSum = new long[n][m];

        // Base cases (j=0, i.e., 2^0 = 1 node path)
        for (int i = 0; i < n; i++) {
            nextPlayer[i][0] = receiver[i];
            pathSum[i][0] = i;
        }

        // Precomputation using DP
        for (int j = 1; j < m; j++) {
            for (int i = 0; i < n; i++) {
                int prevHalfEndNode = nextPlayer[i][j - 1];
                nextPlayer[i][j] = nextPlayer[prevHalfEndNode][j - 1];
                pathSum[i][j] = pathSum[i][j - 1] + pathSum[prevHalfEndNode][j - 1];
            }
        }

        long maxScore = 0;
        // The total number of players in the sum is k+1 (k passes + 1 start player)
        long pathLength = k + 1;

        for (int i = 0; i < n; i++) {
            long currentScore = 0;
            int currentPlayer = i;
            long len = pathLength;

            for (int j = m - 1; j >= 0; j--) {
                if ((len >> j & 1) == 1) {
                    currentScore += pathSum[currentPlayer][j];
                    currentPlayer = nextPlayer[currentPlayer][j];
                }
            }
            maxScore = Math.max(maxScore, currentScore);
        }

        return maxScore;
    }
}
```
### Algorithm
1.  **Precomputation:**
    - Determine the maximum power of two needed, `m`, which is approximately `log2(k)`.
    - Create two 2D arrays: `nextPlayer[n][m]` to store the destination after `2^j` steps, and `pathSum[n][m]` to store the sum of indices over a path of `2^j` steps.
    - Initialize the base cases for `j=0` (path of length `2^0 = 1`):
        - `nextPlayer[i][0] = receiver[i]`
        - `pathSum[i][0] = i`
    - Use dynamic programming to fill the tables for `j` from `1` to `m-1`:
        - `nextPlayer[i][j] = nextPlayer[nextPlayer[i][j-1]][j-1]`
        - `pathSum[i][j] = pathSum[i][j-1] + pathSum[nextPlayer[i][j-1]][j-1]`
2.  **Querying:**
    - Initialize `max_score = 0`.
    - For each player `i` from `0` to `n-1`:
        - Calculate the score for a path of length `k+1` (for `k` passes).
        - Use the binary representation of `k+1` to assemble the path from the precomputed segments.
        - Iterate `j` from `m-1` down to `0`. If the `j`-th bit of `k+1` is set, add the corresponding `pathSum` and advance the `currentPlayer`.
        - Update `max_score` with the calculated score for starting player `i`.
3.  Return `max_score`.

# Solutions
### Java

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

```

### CPP

```cpp
class Solution {
public:
  long long getMaxFunctionValue(vector<int> &receiver, long long k) {
    int n = receiver.size(), m = 64 - __builtin_clzll(k);
    int f[n][m];
    long long g[n][m];
    for (int i = 0; i < n; ++i) {
      f[i][0] = receiver[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 long ans = 0;
    for (int i = 0; i < n; ++i) {
      int p = i;
      long long t = 0;
      for (int j = 0; j < m; ++j) {
        if (k >> j & 1) {
          t += g[p][j];
          p = f[p][j];
        }
      }
      ans = max(ans, p + t);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def getMaxFunctionValue(self, receiver: List[int], k: int) -> int: n, m = len(receiver), k . bit_length() f = [[0] * m for _ in range(n)] g = [[0] * m for _ in range(n)] for i, x in enumerate(receiver): f[i][0] = x g[i][0] = i for j in range(1, m): for i in range(n): f[i][j] = f[f[i][j - 1]][j - 1] g[i][j] = g[i][j - 1] + g[f[i][j - 1]][j - 1] ans = 0 for i in range(n): p, t = i, 0 for j in range(m): if k >> j & 1: t += g[p][j] p = f[p][j] ans = max(ans, t + p) return ans

```