# 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 earliestAndLatest(int n, int firstPlayer, int secondPlayer) { dp.resize(n + 1, vector>(n + 1, vector

(n + 1))); const auto [a, b] = solve(firstPlayer, n - secondPlayer + 1, n); return {a, b}; } private: typedef pair 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>> 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(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]; 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 + 1); b = Math.max(b, res + 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 @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)