[Python] Simple dp+memo
there are 4 situations:\n1.     [                    mid                  ]\n1.       a       b \n2.                                      a     b\n3.       a   
there are 4 situations:\n1.     [                    mid                  ]\n1.       a       b \n2.                                      a     b\n3.       a                         b\n4.                    a                       b\n\nAccording to the principle of symmetry, we can reduce them to these two situations:\n1.     [                    mid                  ]\n2.       a       b \n3.       a                           b\n\nThere for we just need to translate firstPlayer and secondPlayer to these two situations and do operations on them.\n\nEach round, we try to reduce n players into ceil(n/2) players.\n\nFor the first situation, for players before A, No matter how these players are combined, their impact on the entire formation depends only on how many players win on the left and how many players win on the right. For the players who win on the right, we will decrease the indexes of A and B at the same time. There are (n-1) possibilities. In each possibility, we perform the same operation on the players between A and B, and correspondingly decrease the index of b (because the operation is performed on the players between A and B, the index of player A would not be changed.)\n```\nfor i in range(a):\n\tfor j in range(b-a):\n\t\tl = min(l,self.earliestAndLatest(mid,a-i,b-i-j)[0])\n\t\tr = max(r,self.earliestAndLatest(mid,a-i,b-i-j)[1])  \n```\nFor the second situation, the index of B is greater than the index of mid. If all battles are won by the left player, then B\'s position in the next round should be the last of array. Based on this point, we can perform the same operation on them, and we can get the following code.\n```\nfor i in range(a):\n\tfor j in range(c-a):\n\t\tl = min(l,self.earliestAndLatest(mid,a-i,mid-i-j)[0])\n\t\tr = max(r,self.earliestAndLatest(mid,a-i,mid-i-j)[1])\n```\n\nEnumerate and select the smallest earlier round and the largest latest round to get the answer we want.\nTC: \nFor earliestAndLatest( n, firstPlayer, secondPlayer): O(log n*n^2)\nThe loop in function takes O(n^2)\n=> O(n^4 logn)\nSC:\n=> O(n^2 logn)\n\n\n```\nclass Solution:\n    @lru_cache(None)\n    def earliestAndLatest(self, n: int, firstPlayer: int, secondPlayer: int) -> List[int]:\n        if firstPlayer + secondPlayer == n + 1:\n            return [1,1]\n        a,b = min(firstPlayer, secondPlayer), max(firstPlayer, secondPlayer)\n        mid = ceil(n/2)\n        l = inf\n        r = -inf\n        if b<=mid or a>mid:\n            if a>mid:\n                a,b = n+1-b,n+1-a\n            for i in range(a):\n                for j in range(b-a):\n                    l = min(l,self.earliestAndLatest(mid,a-i,b-i-j)[0])\n                    r = max(r,self.earliestAndLatest(mid,a-i,b-i-j)[1])  \n        else:\n            if n+1-b < a:\n                a,b = n+1-b,n+1-a\n            c = n+1-b\n            for i in range(a):\n                for j in range(c-a):\n                    l = min(l,self.earliestAndLatest(mid,a-i,mid-i-j)[0])\n                    r = max(r,self.earliestAndLatest(mid,a-i,mid-i-j)[1])\n        return [l+1,r+1]\n```
[]