We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximize Value of Function in a Ball Passing Game

Number: 3032

Difficulty: Hard

Paid? No

Companies: Oracle

Problem Description

You are given an array receiver of length n and an integer k. There are n players (indexed from 0 to n−1) taking part in a ball-passing game. You choose a starting player i and then perform k passes such that the ball moves from player i to receiver[i], then to receiver[receiver[i]], and so on. The score of the game is the sum of the indices of all players who touched the ball (including repetitions and the starting player). The goal is to find the maximum possible score that can be achieved by choosing an optimal starting player.

Key Insights

  • The passing sequence is defined by the receiver array, forming a directed graph with outdegree 1. Every sequence eventually falls into a cycle.
  • Because k can be very large (up to 1e10), a simulation of k passes is not possible; instead, use a doubling technique (binary lifting) to "jump" many passes at once.
  • Precompute, for each node (player) and for powers-of-two number of passes, both the destination and the cumulative score.
  • For each starting player, build the final result by decomposing k into powers of two and accumulating the sums, then take the maximum score among all starting players.

Space and Time Complexity

Time Complexity: O(n log k), where n is the number of players and log k is the number of binary lifting steps. Space Complexity: O(n log k) for storing the doubling table.

Solution

We use a binary lifting (doubling) approach. For each player i, we want to know:

  1. The player reached after making 2^j passes.
  2. The cumulative sum of indices encountered during these passes (excluding the starting player in the first table entry if we treat it consistently).

The idea is to build a table dp[j][i] where:

  • dp[0][i] = (receiver[i], receiver[i]) for one pass.
  • For j > 0, dp[j][i] is computed by combining dp[j-1][i] and dp[j-1] of the resulting node:
    • next = dp[j-1][ dp[j-1][i].first ].first
    • sum = dp[j-1][i].second + dp[j-1][ dp[j-1][i].first ].second

After building the table for all j up to log2(k), for each starting player i, we initialize the total score with i (since the starting player touches the ball) and then simulate the remaining k passes by checking every bit of k. For every set bit at position j, we update the current state and add the corresponding sum. Finally, we choose the maximum score over all starting players.

Code Solutions

# Python implementation with detailed comments.

def maximize_score(receiver, k):
    n = len(receiver)
    # Determine the maximum power needed for binary lifting.
    max_power = 0
    temp = k
    while temp:
        max_power += 1
        temp //= 2

    # Initialize dp table.
    # dp[j][i] = (next_index, cumulative_sum) after 2^j passes from i.
    dp = [[(0, 0)] * n for _ in range(max_power)]
    
    # Base case: For one pass (2^0), next node is receiver[i] and sum is receiver[i].
    for i in range(n):
        dp[0][i] = (receiver[i], receiver[i])
    
    # Build doubling table.
    for j in range(1, max_power):
        for i in range(n):
            next_node, sum1 = dp[j-1][i]
            next_next, sum2 = dp[j-1][next_node]
            dp[j][i] = (next_next, sum1 + sum2)
    
    max_score = float('-inf')
    
    # For every starting player, simulate the ball passing using doubling.
    for i in range(n):
        current_score = i  # starting player's index is added.
        current_node = i
        remaining_passes = k
        
        power = 0
        while remaining_passes:
            if remaining_passes & 1:
                next_node, add_sum = dp[power][current_node]
                current_score += add_sum
                current_node = next_node
            remaining_passes //= 2
            power += 1
        max_score = max(max_score, current_score)
    
    return max_score

# Example usage:
receiver1 = [2, 0, 1]
k1 = 4
print(maximize_score(receiver1, k1))  # Expected output: 6

receiver2 = [1, 1, 1, 2, 3]
k2 = 3
print(maximize_score(receiver2, k2))  # Expected output: 10
← Back to All Questions