[Python] 2 Solution: dfs  and smart dp, explained
Not very difficult problem, the main problem in python to make it work without TLE. Let us use dfs(pos, i) function, where:\n1. pos is tuple of players we still
Not very difficult problem, the main problem in python to make it work without TLE. Let us use `dfs(pos, i)` function, where:\n1. `pos` is tuple of players we still have.\n2. `i` is how many matches were already played.\n\nEach time we run recursion, check that pair `(firstPlayer, secondPlayer)` is not here yet (denoted by `F` and `S`), if it is, add number of matches played to set `ans` and return. Also, ignore pairs where one of the two players is `S` or `F`. Finally, use functionality of python `product` function to fastly generate all next positions.\n\n#### Complexity\nWe have `n` players in the beginning, and we have `n//2` pairs, so there is `O(2^(n//2))` options for the first step, then it will be `O(2^(n//4))` and so on, so in the end we can have potentially `O(2^n)` positions, which is our time complexity. However, due to careful prunning, it practice it is much less, like if we have `28`, then on the next step we have not `2^14`, but `2^12` positions, because `S` and `F` always go to the next match or we stop, then we have `2^5` and then we have `2^1`, so it is more like `2^(12 + 5 + 1) = 2^18`, so it is still feasible. Space complexity is `O(n)`.\n\n#### Code\n```python\nclass Solution:\n    def earliestAndLatest(self, n, F, S):\n        ans = set()\n        def dfs(pos, i):\n            M, pairs = len(pos), []\n            if M < 2: return\n\n            for j in range(M//2):\n                a, b = pos[j], pos[-1-j]\n                if (a, b) == (F, S):\n                    ans.add(i)\n                    return\n                if a != F and b != F and a != S and b != S:\n                    pairs.append((a, b))\n\n            addon = (F, S) if M%2 == 0 else tuple(set([F, S, pos[M//2]]))\n            for elem in product(*pairs):\n                dfs(sorted(elem + addon), i + 1)\n\n        dfs(list(range(1, n+1)), 1)\n        return [min(ans), max(ans)]\n```\n\n#### Solution 2\nThis solution is borrowed from https://leetcode.com/problems/the-earliest-and-latest-rounds-where-players-compete/discuss/1268560/Python-simple-top-down-dp-solution-O(N4*logN), here I just rewrote it a bit and try to add some explanations with examples. Please go and upvote this post, it deserves more upvotes.\n\nDefine by `dp(l, r, m, q)` state with the following parameters:\n\n1. `l` and `r` are positions of our `F` and `S` players from start and from end. For example if we have 1, 2, **3**, 4, 5, 6, **7**, 8, 9, 10, 11, 12, where we denoted by bold elements the first and the second player, and we have `l = 3` and `r = 6`.\n2. `m` is current number of players, we have 12 here and `q` is number of games already played.\n\nWhat can happen on the next step? Let us go through options and see what is going on. Let us denote by underline  <u>x</u> the players who loose and by **x** player who win.\nThen at the moment we have the following situation:\n\n1, 2, **3**, 4, 5, <u>6</u>, **7**, 8, 9, <u>10</u>, 11, 12.\n\nWhat can happen that among players `1` and `2` there can be zero, one or two wins, and actually it does not matter which ones. Let us consider the cases:\n\n1. We have zero wins, so we have <u>1</u>, <u>2</u>, **3**, 4, 5, <u>6</u>, **7**, 8, 9, <u>10</u>, **11**, **12**. Then what we know for sure is in new round player **3** will be the first. Player **7** can be either 3, 4 or 5 from the end.\n2. We have one wins, so we have <u>1</u>, **2**, **3**, 4, 5, <u>6</u>, **7**, 8, 9, <u>10</u>, <u>11</u>, **12**. Then what we know for sure is in new round player **3** will be the second. Player **7** can be either 2, 3 or 4 from the end.\n3. We have two wins, so we have **1**, **2**, **3**, 4, 5, <u>6</u>, **7**, 8, 9, <u>10</u>, <u>11</u>, <u>12</u>. Then what we know for sure is in new round player **3** will be the third. Player **7** can be either 1, 2 or 3 from the end.\n\nSo, what we need to do is to carefully understand all the cases we can meet.\n\n#### Complexity\nWe have `O(n^2*log(n)` states: `O(n)` for both `l` and `r` and `log(n)` states for `m`, which will define `q` in unique way. We have `O(n^2)` transactions from one state to others, so time complexity is `O(n^4*log n)`, space complexity is `O(n^2*log n)`. Actually, more detailed analysis shows that log factor can be removed, because say `n = 64`, then we have `O(64*64)` states for `m = 64`, then we have `O(32*32)` states for `m = 32` and so on. So final time complexity is `O(n^4)`, space is `O(n^2)`.\n\n#### Code\n```python\nclass Solution:\n    def earliestAndLatest(self, n, F, S):\n        @lru_cache(None)\n        def dp(l, r, m, q):\n            if l > r:  dp(r, l, m, q)\n            if l == r: ans.add(q)\n            \n            for i in range(1, l + 1):\n                for j in range(l-i+1, r-i+1):\n                    if not (m+1)//2 >= i + j >= l + r - m//2: continue\n                    dp(i, j, (m + 1) // 2, q + 1)\n        \n        ans = set()\n        dp(F, n - S + 1, n, 1)\n        return [min(ans), max(ans)]\n```\n\nIf you have any questions, feel free to ask. If you like solution and explanations, please **Upvote!**
['Depth-First Search']