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 the Minimum Game Score

Number: 3762

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

You are given an array points (of size n) and an integer m. There is an initially zero‐filled array gameScore (of size n). You start “before” index 0 (i = –1) and may make at most m moves. In each move you may either increase the index by 1 or decrease it by 1 – but after the first move the index must always remain between 0 and n–1. When you “visit” an index i (that is, when you move into it) you add points[i] to gameScore[i]. Your goal is to plan a route so that after at most m moves the minimum score in gameScore is as high as possible. Return that maximum possible minimum value.

For example, with points = [2,4] and m = 3 one best sequence is: –1→0 (score becomes [2,0]), 0→1 (score becomes [2,4]), and 1→0 (score becomes [4,4]). The minimum gameScore is 4.

Key Insights

  • We must “visit” every index at least once (the natural route from 0 to n–1) so that every gameScore gets at least one addition.
  • Revisiting an index is allowed. Every extra visit increases gameScore[i] by points[i]. To make every gameScore[i] at least x we need at least ceil(x/points[i]) visits at index i.
  • The “baseline” route (without any detours) gives one visit per index; extra visits must be “detoured” into the route.
  • A detour normally costs extra moves. However, if planned at a turning‐point the extra visit can “cost” one move rather than a full round‐trip costing two moves.
  • Thus for each index i let r = (ceil(x/points[i]) – 1) be the additional number of visits needed beyond the baseline. By “assigning” a free detour when we reverse direction at that index, the extra move cost at index i is 2*r – 1 (if r > 0) and 0 otherwise.
  • The overall moves used include the baseline moves needed to simply cover a route (from –1 to 0 and then between indices – which sums to n moves) plus the extra moves needed for detours.
  • We then “binary search” on x (the candidate minimum score) and use a greedy check that x is achievable if:
      baselineCost + Σ[for each index i where r > 0] (2*r – 1) ≤ m.

Space and Time Complexity

Time Complexity: O(n log(maxScore)) where maxScore is an upper–bound on the answer (for each candidate x we scan the n elements and binary search over about log(maxScore) candidates).
Space Complexity: O(1) extra space (apart from input arrays).

Solution

We first observe that if we want gameScore[i] ≥ x then index i must be visited at least visitsNeeded[i] = ceil(x/points[i]) times. Since a simple route from index –1 to 0 and then moving “forward” can deliver one visit per index (costing n moves in total), we denote extraVisitsNeeded[i] = visitsNeeded[i] – 1. In a route on a line, performing a “detour” to harvest an extra visit (re–visiting an index that is a turning–point) costs 1 extra move rather than 2 moves for a full round–trip. Thus we assume that for an index that needs extra visits, one of them may be “free” (i.e. costs only one extra move) while every additional extra visit costs 2 moves. So the extra move cost per index is:
  if r = extraVisitsNeeded[i] > 0 then cost = 2 * r – 1, else 0. In addition we must pay the baseline cost of n moves (remember: move from –1 to 0 plus “step–moves” when traversing the array). We then check for a candidate x whether
  totalCost = baselineCost + Σ(for each i, cost[i]) ≤ m. If yes, then it is possible to achieve a minimum gameScore of x; if not, it isn’t. Finally, we use binary search on x to get the maximum possible minimum score.

Below are code solutions with detailed line–by–line comments in several languages.

Code Solutions

# Function to check if candidate minimum score x is achievable with at most m moves.
import math
def canAchieve(x, points, m):
    n = len(points)
    # baseline cost: from starting index -1 to 0 costs 1 move plus moving from 0 to n-1 costs (n-1) moves
    baseline = n  
    extra_cost = 0
    for pt in points:
        # compute how many visits are needed at this index to have score at least x.
        # Since one visit is provided by the baseline route, extra visits needed are:
        req = math.ceil(x / pt) - 1  
        if req > 0:
            # extra cost: the first extra visit costs 1 move (as a detour at a turning point),
            # and every additional extra visit costs 2 moves.
            extra_cost += (2 * req - 1)
    total_moves = baseline + extra_cost
    return total_moves <= m

def maximizeMinGameScore(points, m):
    # lower bound can be 0 and upper bound can be set high; 
    # since each visit to index i adds points[i], an upper bound for gameScore[i] is points[i] * (m) theoretically.
    low, high = 0, max(points) * m  
    ans = 0
    while low <= high:
        mid = (low + high) // 2
        if canAchieve(mid, points, m):
            ans = mid
            low = mid + 1
        else:
            high = mid - 1
    return ans

# Example usage:
print(maximizeMinGameScore([2,4], 3))   # Expected output: 4
print(maximizeMinGameScore([1,2,3], 5))   # Expected output: 2
← Back to All Questions