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
class Solution {
 public:
  vector<int> earliestAndLatest(int n, int firstPlayer, int secondPlayer) {
    dp.resize(n + 1, vector<vector<P>>(n + 1, vector<P>(n + 1)));
    const auto [a, b] = solve(firstPlayer, n - secondPlayer + 1, n);
    return {a, b};
  }

 private:
  typedef pair<int, int> P;
  // dp[i][j][k] := (earliest, latest) pair w/ firstPlayer is i-th player from
  // Front, secondPlayer is j-th player from end, and there're k people
  vector<vector<vector<P>>> dp;

  P solve(int l, int r, int k) {
    if (l == r)
      return {1, 1};
    if (l > r)
      swap(l, r);
    if (dp[l][r][k] != pair<int, int>(0, 0))
      return dp[l][r][k];

    int a = INT_MAX;
    int b = INT_MIN;

    // Enumerate all 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);
        a = min(a, x + 1);
        b = max(b, y + 1);
      }

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

  // dp[i][j][k] := (earliest, latest) pair w/ firstPlayer is i-th player from
  // Front, secondPlayer is j-th player from end, and there're k people
  private int[][][][] dp;

  private int[] solve(int l, int r, int k) {
    if (l == r)
      return new int[] {1, 1};
    if (l > r)
      return solve(r, l, k);
    if (!Arrays.equals(dp[l][r][k], new int[] {0, 0}))
      return dp[l][r][k];

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

    // Enumerate all 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);
        a = Math.min(a, res[0] + 1);
        b = Math.max(b, res[1] + 1);
      }

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

      a = math.inf
      b = -math.inf

      # Enumerate all 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)