[Python] - O(N^4) - Generate and Test + Explanation
The basic stratgy is as follows: Given the postions of the two players in round N and round N+1, can you determine if it possible to transition from the old to 
The basic stratgy is as follows: **Given the postions of the two players in round N and round N+1, can you determine if it possible to transition from the old to new configuration?** *A configuration is represented with only the positions of the two top players.*\n\nImagine this test takes time f(n). Then, we can generate all possible configurations in the next round (N choose 2 which is O(N^2)) and see if any of the configurations in the previous round (also O(N^2) for same reason) that can be reached from the starting configuration can transition to this new configuration. If we move into a configuration where the two champs play each other, we don\'t add it to our list, and we check to see if that is the earliest they play (that test is done by **bigmatchplayed**). This **generate and test** strategy is implemented in **earliestAndLatest**\n\nThis gives runtime O(N^4 x f(N)). With some maths, you can create an O(1) test.\nI call this test **canReach**. Below are some of the basic points behind the logic: \n* First, create a **new representation** for the configuration. Instead of a pair of locations of the first and second player (along with how many people are in the round), we can represent the state as a **triple (a,b,c)** where **a** represents the number of people before the first player, **b** is the number of people between the first and second, and **c** is the number of people after the second. **a+1** = first person, **a+1+b+1** = second person, n-second person = **c**. This representation is computed by **abc**\n![image](https://assets.leetcode.com/users/images/4ee00b40-b083-4ca1-9157-a3dd97b87d6c_1624269865.709154.png)\n\n\n* When we play a round, we can imagine that the line of players is folded in half as seen in the image. I have denoted where regions a,b and c are, and the \'x\'s correspond to where the top players are. We can see in this example that several regions are created, such as the top region \'a\', the middle region \'l1\' and the bottom region \'l2\'. At the end of the round, we must decide how many players from each side wins from each region. **It doesn\'t matter who those players are, just how many from each side, as the effect is the same.**\n* **There are different images/cases**. We can have the \'x\'s on different sides of the U (Case 1), or on the same side (Case 2). For convenience, the case of them being on the same side can be reduced to them being on the left side (and when they are on the right, we flip the players). We could even have one player in the middle (Case 3)\n* In some regions, like l2, it doesn\'t matter what our selection is. If we look at what happens at the U at the bottom, the middle person stays regardless, and then we must eliminate l2 players. So we will always delete l2 from the U ring (and thus l2 from **b**)\n* In other regions, like region \'a\' and \'l1\', it does matter. I denote how many have won in these regions by **alpha** and **beta** respectively.\n* From these type of diagrams, we can derive relationships between *a*,*b*,*c* of the old and new configurations, *l1*,*l2*,*l3* (regions in the old configuration) and *alpha* and *beta* which is the number of players that won in specific regions.\n* The test will then involve checking that:\n\t* Alpha and beta are not too small (non negative) and not too large (not larger than the region they a related to\n\t* The new **a,b,c** is not too small (non negative) and not too large (not greater than the old **a,b,c** and sums to the right amount)\n\n```python\nclass Solution:\n    def earliestAndLatest(self, n: int, firstPlayer: int, secondPlayer: int) -> List[int]:\n        setup = (firstPlayer, secondPlayer)\n        if firstPlayer > secondPlayer:\n            setup = self.flip(setup, n)\n        lastlayer = [setup]\n        roundn = 1\n        earliest = 1 if self.bigmatchplayed(setup, n) else None\n        nold = n\n        if(earliest == 1):\n            return [1, 1]\n        while lastlayer != []:\n            roundn = roundn+1\n            nextlayer = []\n            np = nold//2+(nold % 2)\n            for i in range(1, np):\n                for j in range(i+1, np+1):\n                    newloc = (i, j)\n                    for prev in lastlayer:\n                        if(self.canReach(prev, newloc, nold)):\n                            if self.bigmatchplayed(newloc, np):\n                                if earliest == None:\n                                    earliest = roundn\n                            else:\n                                nextlayer.append(newloc)\n                                break\n            lastlayer = nextlayer\n            nold = np\n\n        return [earliest, roundn]\n\n    def canReach(self, oldLoc, newLoc, n):\n        mid = (n+1)/2\n        (a, b, c) = self.abc(oldLoc, n)\n        (ap, bp, cp) = self.abc(newLoc, n//2+(n % 2))\n        if not (0 <= ap <= a and 0 <= bp <= b):\n            return False\n        if(oldLoc[0] < mid and oldLoc[1] > mid and (oldLoc[0] < n+1-oldLoc[1])): #case 1\n            l1 = c-a-1\n            l2 = (b-l1-1-(n % 2))//2\n            alpha = a-ap\n            beta = bp-b+l2+l1+1\n            return (0 <= alpha+beta <= c and 0 <= alpha <= a and 0 <= beta <= l1)\n        if(oldLoc[0] < mid and oldLoc[1] < mid): #case 2\n            l3 = a\n            l2 = b\n            l1 = (c-l2-l3-2-(n % 2))//2\n            alpha = a-ap\n            beta = b-bp\n            return (0 <= c-l1-beta-alpha-2 <= c)\n        if(oldLoc[0] < mid and oldLoc[1] == mid): # case 3\n            return True\n        return self.canReach(self.flip(oldLoc, n), self.flip(newLoc, n//2+(n % 2)), n)\n\n    def flip(self, loc, n):\n        return (n+1-loc[1], n+1-loc[0])\n\n    def abc(self, loc, n):\n        return (loc[0]-1, loc[1]-loc[0]-1, n-loc[1])\n\n    def bigmatchplayed(self, location, size):\n        return location[0] == size+1-location[1]\n```\n\nIf you have any feedback (on logic, code or explanation) that would be great
['Python']