Skip to content

1900. The Earliest and Latest Rounds Where Players Compete 👍

  • Time: $O(n^4)$
  • Space: $O(n^2)$
 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
class Solution {
 public:
  vector<int> earliestAndLatest(int n, int firstPlayer, int secondPlayer) {
    using P = pair<int, int>;
    vector<vector<vector<P>>> mem(n + 1,
                                  vector<vector<P>>(n + 1, vector<P>(n + 1)));
    const auto [a, b] = solve(firstPlayer, n - secondPlayer + 1, n, mem);
    return {a, b};
  }

 private:
  // Returns the (earliest, latest) pair, the first player is the l-th player
  // from the front, the second player is the r-th player from the end, and
  // there're k people.
  pair<int, int> solve(int l, int r, int k,
                       vector<vector<vector<pair<int, int>>>>& mem) {
    if (l == r)
      return {1, 1};
    if (l > r)
      swap(l, r);
    if (mem[l][r][k] != pair<int, int>{0, 0})
      return mem[l][r][k];

    int a = INT_MAX;
    int b = INT_MIN;

    // Enumerate all the possible positions.
    for (int i = 1; i <= l; ++i)
      for (int j = l - i + 1; j <= r - i; ++j) {
        if (i + j > (k + 1) / 2 || i + j < l + r - k / 2)
          continue;
        const auto [x, y] = solve(i, j, (k + 1) / 2, mem);
        a = min(a, x + 1);
        b = max(b, y + 1);
      }

    return mem[l][r][k] = {a, b};
  }
};

 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 {
  public int[] earliestAndLatest(int n, int firstPlayer, int secondPlayer) {
    int[][][][] mem = new int[n + 1][n + 1][n + 1][2];
    return solve(firstPlayer, n - secondPlayer + 1, n, mem);
  }

  // Returns the (earliest, latest) pair, the first player is the l-th player
  // from the front, the second player is the r-th player from the end, and
  // there're k people.
  private int[] solve(int l, int r, int k, int[][][][] mem) {
    if (l == r)
      return new int[] {1, 1};
    if (l > r)
      return solve(r, l, k, mem);
    if (!Arrays.equals(mem[l][r][k], new int[] {0, 0}))
      return mem[l][r][k];

    int a = Integer.MAX_VALUE;
    int b = Integer.MIN_VALUE;

    // Enumerate all the possible positions.
    for (int i = 1; i <= l; ++i)
      for (int j = l - i + 1; j <= r - i; ++j) {
        if (i + j > (k + 1) / 2 || i + j < l + r - k / 2)
          continue;
        int[] res = solve(i, j, (k + 1) / 2, mem);
        a = Math.min(a, res[0] + 1);
        b = Math.max(b, res[1] + 1);
      }

    return mem[l][r][k] = new int[] {a, b};
  }
}

 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
class Solution:
  def earliestAndLatest(self, n: int,
                        firstPlayer: int, secondPlayer: int) -> List[int]:
    @functools.lru_cache(None)
    def dp(l: int, r: int, k: int) -> List[int]:
      """
      Returns the (earliest, latest) pair, the first player is the l-th player
      from the front, the second player is the r-th player from the end, and
      there're k people.
      """
      if l == r:
        return [1, 1]
      if l > r:
        return dp(r, l, k)

      a = math.inf
      b = -math.inf

      # Enumerate all the possible positions.
      for i in range(1, l + 1):
        for j in range(l - i + 1, r - i + 1):
          if not l + r - k // 2 <= i + j <= (k + 1) // 2:
            continue
          x, y = dp(i, j, (k + 1) // 2)
          a = min(a, x + 1)
          b = max(b, y + 1)

      return [a, b]

    return dp(firstPlayer, n - secondPlayer + 1, n)