Recursion, Memo and Optimized Recursion
We start with the straightforward recursion, then optimize it using memoisation, and finally arrive at the efficient solution using all that insight we gained. 
> We start with the straightforward recursion, then optimize it using memoisation, and finally arrive at the efficient solution using all that insight we gained. \n\n#### Recursion\nWe try all combinations, and it should work since  `n` is limited to `28`. For the first round, we have no more than 2  ^ 12 choices (14 pairs, and winners are predefined for 2 pairs), second round - 2 ^ 5, then 2 ^ 2, then 1 choice, and finally we will have just two winners left. Therefore, we will have up to 524,288 total combinations and 5 rounds.\n\nThe tricky part is to make it as efficient as possible. For that, I am using `mask` to indicate which players have been eliminated.\n \nWe move `i` and `j` to pick the pairs; when `i >= j`, we start a new round. When `i` and `j` point to our finalists, we update the min and max rounds.\n\n**C++**\n```cpp\nint min_r = INT_MAX, max_r = INT_MIN;\nvoid dfs(int mask, int round, int i, int j, int first, int second) {\n    if (i >= j)\n        dfs(mask, round + 1, 0, 27, first, second);\n    else if ((mask & (1 << i)) == 0)\n        dfs(mask, round, i + 1, j, first, second);\n    else if ((mask & (1 << j)) == 0)\n        dfs(mask, round, i, j - 1, first, second);\n    else if (i == first && j == second) {\n        min_r = min(min_r, round);\n        max_r = max(max_r, round);\n    }\n    else {\n        if (i != first && i != second)\n            dfs(mask ^ (1 << i), round, i + 1, j - 1, first, second);\n        if (j != first && j != second)\n            dfs(mask ^ (1 << j), round, i + 1, j - 1, first, second);\n    }\n}\nvector<int> earliestAndLatest(int n, int first, int second) {\n    dfs((1 << n) - 1, 1, 0, 27, first - 1, second - 1);\n    return { min_r, max_r };\n}\n```\n**Complexity Analysis**\n- Time: O(2 ^ n).\n- Memory: O(log n) for the recursion.\n\n#### Add Memoisation\nI tried to memoise `visited` masks, but it only gave a modest boost. Then I realized that what really matters are the number of players standing before the first (left), in between (mid), and after (right) the second player. So we keep track of `l`, `m`, and `r` - a bit messy but does the job. With this insight, the runtime improved from 500 to 0 ms.\n\n**C++**\n```cpp\nint min_r = INT_MAX, max_r = INT_MIN;\nbool visited[27][27][27] = {};\nvoid dfs(int mask, int round, int i, int j, int first, int second, int l, int m, int r) {\n    if (i >= j)\n        dfs(mask, round + 1, 0, 27, first, second, l, m, r);\n    else if ((mask & (1 << i)) == 0)\n        dfs(mask, round, i + 1, j, first, second, l, m, r);\n    else if ((mask & (1 << j)) == 0)\n        dfs(mask, round, i, j - 1, first, second, l, m, r);\n    else if (i == first && j == second) {\n        min_r = min(min_r, round);\n        max_r = max(max_r, round);\n    }\n    else if (!visited[l][m][r]) {\n        visited[l][m][r] = true;\n        if (i != first && i != second)\n            dfs(mask ^ (1 << i), round, i + 1, j - 1, first, second, \n                l - (i < first), m - (i > first && i < second), r - (i > second));\n        if (j != first && j != second)\n            dfs(mask ^ (1 << j), round, i + 1, j - 1, first, second,\n                l - (j < first), m - (j > first && j < second), r - (j > second));\n    }\n}\nvector<int> earliestAndLatest(int n, int first, int second) {\n    dfs((1 << n) - 1, 1, 0, 27, first - 1, second - 1, first - 1, second - first - 1, n - second);\n    return { min_r, max_r };\n}\n```\n**Complexity Analysis**\n- Time: O(n ^ 3).\n- Memory: O(n ^ 3) for the memoisation.\n\n#### Optimized Recursion\nWith the insight about tracking the number of players between champions, we can simplify the algorithm by computing possible transitions instead of simulating individual competitions. Say, we have 15 total players; 4 players on the left and 5 - on the right (including champions).\n\n![image](https://assets.leetcode.com/users/images/4d495627-d7e9-4227-a518-ec400badf5e0_1623970510.4030144.png)\n\nFor the second round, we will have 8 total players, and two possible cases: `[1, 4]` (or `[4, 1]`) and `[2, 3]` (or `[3, 2]`).\n\n![image](https://assets.leetcode.com/users/images/4af2736a-eadf-4fed-947e-853e8a7d9141_1623971629.9998062.png)\n\nSo, we will track players on the left `l` and right `r`, including champions, and total number of players `n`. If `l == r`, our champions will compete in the current round. \n\nDetermining the valid standings of players `i` and `j` after the round is a bit tricky, but here are ground rules:\n- To simplify the calculation, we always make sure `l < r`. We can do it because reult for `[8, 3]` will be the same as for `[3, 8]`. \n- `i` and `j` should be at least one to account for a champion.\n- Picking `i` players on the left meaning that `l - i` players lose to players on the right.\n\t- So we have to pick `l - i  + 1` players on the right or more (`+1` is for the champion).\n- Winers on the left and right (`i  + j`) should not exceed the number of players in the next round (`(n + 1) / 2`).\n- Loosers on the left and right (`l - i + r - j`) should not exceed the half of players in the current round.\n\n**C++**\n```cpp\nint min_r = INT_MAX, max_r = INT_MIN;\nvoid dfs(int l, int r, int n, int round) {\n    if (l == r) {\n        min_r = min(min_r, round);\n        max_r = max(max_r, round);\n    }\n    else\n        if (l > r)\n            swap(l, r);\n        for (int i = 1; i < l + 1; ++i)\n            for (int j = l - i + 1; i + j <= min(r, (n + 1) / 2); ++j)\n                if (l + r - (i + j) <= n / 2)\n                    dfs(i, j, (n + 1) / 2, round + 1);\n}\nvector<int> earliestAndLatest(int n, int first, int second) {\n    dfs(first, n - second + 1, n, 1);\n    return { min_r, max_r };\n}\n```
['C']