Skip to content

3449. Maximize the Minimum Game Score 👍

  • Time: $\log\left(\frac{m + 1}{2} \cdot \texttt{points[0]}\right)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
 public:
  long long maxScore(vector<int>& points, int m) {
    long l = 0;
    long r = (m + 1L) / 2 * points[0] + 1;

    while (l < r) {
      const long mid = (l + r + 1) / 2;
      if (isPossible(points, mid, m))
        l = mid;
      else
        r = mid - 1;
    }

    return l;
  }

 private:
  // Returns true if it is possible to achieve the maximum minimum value `x`
  // with `m` number of moves.
  bool isPossible(const vector<int>& points, long minVal, long m) {
    long moves = 0;
    long prevMoves = 0;  // to track remaining moves from the previous point
    for (int i = 0; i < points.size(); ++i) {
      // ceil(minVal / point)
      const long required =
          max(0L, (minVal + points[i] - 1) / points[i] - prevMoves);
      if (required > 0) {
        moves += 2L * required - 1;
        prevMoves = required - 1;
      } else if (i + 1 < points.size()) {
        moves += 1;
        prevMoves = 0;
      }
      if (moves > m)
        return false;
    }
    return true;
  };
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
  public long maxScore(int[] points, int m) {
    long l = 0;
    long r = ((long) m + 1) / 2 * points[0] + 1;

    while (l < r) {
      final long mid = (l + r + 1) / 2;
      if (isPossible(points, mid, m))
        l = mid;
      else
        r = mid - 1;
    }

    return l;
  }

  // Returns true if it is possible to achieve the maximum minimum value `x`
  // with `m` number of moves.
  private boolean isPossible(int[] points, long minVal, long m) {
    long moves = 0;
    long prevMoves = 0; // to track remaining moves from the previous point
    for (int i = 0; i < points.length; ++i) {
      // ceil(minVal / point)
      final long required = Math.max(0, (minVal + points[i] - 1) / points[i] - prevMoves);
      if (required > 0) {
        moves += 2L * required - 1;
        prevMoves = required - 1;
      } else if (i + 1 < points.length) {
        moves += 1;
        prevMoves = 0;
      }
      if (moves > m)
        return false;
    }
    return true;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution:
  def maxScore(self, points: list[int], m: int) -> int:
    def isPossible(minVal: int, m: int) -> bool:
      """
      Returns True if it is possible to achieve the maximum minimum value `x`
      with `m` number of moves.
      """
      moves = 0
      prevMoves = 0  # to track remaining moves from the previous point
      for i, point in enumerate(points):
        required = (minVal + point - 1) // point  # ceil(minVal / point)
        required = max(0, required - prevMoves)
        if required > 0:
          moves += 2 * required - 1
          prevMoves = required - 1
        elif i + 1 < len(points):
          moves += 1
          prevMoves = 0
        if moves > m:
          return False
      return True

    l = 0
    r = (m + 1) // 2 * points[0] + 1

    while l < r:
      mid = (l + r + 1) // 2
      if isPossible(mid, m):
        l = mid
      else:
        r = mid - 1

    return l