a
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nimport java.util.*;\n\n\npublic class Solution {\n\n    // every round we remove N/2 people\n    // for A and B to play together the MID must be between them; so they must be at same dist from MID to play\n\n    // Input: n = 11, firstPlayer = 2, secondPlayer = 4            // Output: [3,4]\n    // Explanation:\n    // One possible scenario which leads to the earliest round number:\n    // 1 round: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11\n    // 2 round:    2, 3, 4, 5, 6, 11\n    // 3 round:    2, 3, 4\n\n    //          1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11\n    //          1, 2, 3, 4, 5, 6\n    //          1, 2, 3\n\n    // One possible scenario which leads to the latest round number:\n    // 1 round: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11\n    // 2 round: 1, 2, 3, 4, 5, 6\n    // 3 round: 1, 2, 4\n    // Fourth round: 2, 4\n\n    // Step 1: Think of brute-force solution: we can encode the state in 1 INT; 32 bits so we dont do arraylist work\n    // Step 2: Simplify the problem !!! Notice: SYMMETRY !!!!!\n    // xxxx A xxx B\' xxx M xxx  B xxxx A\' ========= xxxx A\' xxx B xxx M xxx  B\' xxxx A\n    //  we can flip left/right sides; we can also flip A and B !!!!!!!!       always take A < B\n    //  so we can always convert the problem into the order ....A......B.....M;  BOTH ON LEFT never work with both on RIGHT\n\n    // Step 3: solve  RECURSIVELY adjusting indexes\n\n    // NOTICE: 2 cases for A,B and MID:\n    // 1) A,B on same side of MID\n    // xxxx A xxx B xxx M xxx  B\' xxxx A\'\n    //  X      Y     Z\n    // dp[n][a][b] -> dp[(n+1)/2][x+1][x+1+y+1]\n\n    // 2) A,B on DIFF side of MID;  CASE 2:\n    // xxxx A xxx B\' xxx M xxx  B xxxx A\'\n    //  X      Y      Z       = 3 groups of people we can retain; enumerate all possible values for those at each step !!!\n    // and update the next indexes for A,B e.g.\n    // dp[n][a][b]  -> dp[(n+1)/2][x+1][x+1+y+1+z]\n\n\n    public int[] earliestAndLatest(int n, int a, int b) {\n        dp = new int[n + 1][n + 1][n + 1][2];\n        return recMemo(n, a, b);\n    }\n\n    int[] recMemo(int n, int a, int b) {\n        if (n == 2 || a + b == n + 1) return new int[]{1, 1}; // they are fighting now\n        if (dp[n][a][b][0] != 0) return dp[n][a][b];\n        if (a > b) return recMemo(n, b, a); // reverse A,B so A < B always\n        if (a + b > n + 1) return recMemo(n, n - b + 1, n - a + 1); // reverse left,right so always A...B..M\n        // also remap:  1,A,3,4,B ->  B,A,3,4,5 -> A,B,3,4,5\n\n        int nextN = (n + 1) / 2; // also mid\n        dp[n][a][b][0] = Integer.MAX_VALUE / 2;\n        dp[n][a][b][1] = Integer.MIN_VALUE / 2;\n\n        if (b <= nextN) { // case 1: xxxx A xxx B xxx M xxx  B\' xxxx A\'\n            for (int x = 0; x < a; x++) {\n                for (int y = 0; y < b - a; y++) {\n                    int[] case1 = recMemo(nextN, x + 1, x + 1 + y + 1);\n                    dp[n][a][b][0] = Math.min(dp[n][a][b][0], 1 + case1[0]);\n                    dp[n][a][b][1] = Math.max(dp[n][a][b][1], 1 + case1[1]);\n                }\n            }\n        } else { // case 2:  xxxx A xxx B\' xxx M xxx  B xxxx A\'\n            int bb = n + 1 - b;\n            for (int x = 0; x < a; x++) {\n                for (int y = 0; y < bb - a; y++) {\n                    int bToBb = b - bb - 1;\n                    int z = (bToBb + 1) / 2;\n                    int[] case2 = recMemo(nextN, x + 1, x + 1 + y + 1 + z);\n                    dp[n][a][b][0] = Math.min(dp[n][a][b][0], 1 + case2[0]);\n                    dp[n][a][b][1] = Math.max(dp[n][a][b][1], 1 + case2[1]);\n                }\n            }\n        }\n\n        return dp[n][a][b];\n    }\n\n    //   A     B\n    // 1,2,3,4,5     -->        \n\n    int[][][][] dp;\n\n\n}\n\n\n```
['Java']