Python 3: FT 100%: TC O(N**4), SC O(N**2): State Transitions and BFS
Welcome to my ~11th FT 100%\n\n# Intuition\n\nThe first in the line fights the last in line, then second fights second to last, etc.\n\nNot sure why I keep sayi
Welcome to my ~11th FT 100%\n\n# Intuition\n\nThe first in the line fights the last in line, then second fights second to last, etc.\n\nNot sure why I keep saying "fight." Maybe [I\'m feeling violent](https://www.youtube.com/watch?v=8vx_WqwKb74&t=39s)? idk lol\n\nAnyway after we determine a pattern for who wins and loses, we\'ll have\n* some number of people before `first`\n* then `first`\n* more people\n* `second`\n* and a bunch of people on the right\n\nThe pattern will look like this:\n```a\nL first L-R-2 second R\n```\n\n## Step 1: Indistinct People, Canonical L >= R\n\nWe know that people in front will fight people at the back. If we flip the array then it won\'t change the outcomes because the problem doesn\'t depend on first versus second or vice-versa, and it also doesn\'t depend on who exactly the other people are.\n\nTherefore we can\n* summarize the current state as `L first L-R-2 second R`\n* and also treat all the non-first-or-second people as indistinguishable. Only the number of people relative to first and second matter, not their numbers.\n\nTo simplify logic we\'ll pick `L >= R` as our convention. If not, just flip the array (conceptually).\n\n## Step 2: Find the Pattern\n\nIf we have `L == R` then we know this is the round where first and last will fight, so we\'re done.\n\nThus we continue with `L > R`.\n\nIn this situation the first `R` and last `R` fight each other. There are many possible outcomes. But we only care about the *number* of winners on the left versus right. So let\'s call `wl` the number of these `R` fights that result in the left person winning.\n\nThen that leaves an interior region in the array that looks like this:\n```a\n   L-1-R first n-L-R-2\n     ML           MR\n```\n\nThe first part, `R` people, have been handled with the `wl` stuff. The last part `second R` has been handled with the `wl` stuff as well.\n\nWe now have `ML` elements left of `first` and `MR` elements on the right of `first` as labeled above. There are three cases:\n* `ML < MR`: we have `ML` fights with people left of `first`, which can resolve to `0..ML` people remaining left of first\n* `ML == MR`: same as `ML < MR`: they all fight and `first` continues without fighting anyone\n* `ML > MR`: this time we have `MR` fights with people left of `first`, so there can be `0..MR` winners that stay left. Let\'s call that `wl2`, "winners on the left in the second set of fights we care about." Regardless of those these play out, there are still another `ML-1-MR` pairs of people on the left before first. They will fight each other such that `ceil((ML-1-MR)/2)` of them proceed to the next round, all on the left of `first`\n\n## Simplify Logic\n\nThe last paragraph is pretty nasty.\n\nBut we see there\'s a pattern:\n* if `ML <= MR` then `wl2 = 0..ML`, and those are the only people on the left from the interior of the array\n* if `ML > MR` then `wl2 = 0..MR` and there are an extra `ceil((ML-MR-1)/2)` people on the left\n\nSo we can\n* run `wl2 = 0..min(ML, MR)`\n* set `extraLeft = 0 if ML <= MR else ceil((ML-MR-1)/2)`\n* then use the same loop to handle all `ML, MR` relations\n\nThe new states available have\n* `wl + wl2 + extraLeft` people on the left (see above)\n* then `first`\n* then some number of people (which we don\'t need to calculate!)\n* then `second`\n* then `R-wl` people: if `wl` of the `R` fights were won by left people, then `wl` right people lost\n\nThis keeps the loop code simple... although it\'s not *actually* simple to derive this, takes a lot of detailed thinking to get it all exactly right. Hence the extremely high docs:code ratio as I figured it out!\n\n# Approach\n\nFrom the Intuition section we have a way to start from any current state and get new states.\n\nNow we just use BFS:\n* start with `first-1, n-second` to count the people left and right, `n` is the starting value\n* then in each round of BFS:\n  * if `L==R` then this state ends, `first` and `second` fight in this round\n  * otherwise find all the possible resulting states, an `O(N**2)` and enqueue them if we haven\'t already seen them *for this current `n`*\n  * at the end of each BFS level, we know that there were `n//2` fights and thus `n//2` losers, so `n -= n//2`\n\nFinally we just record the first and last round where we found `L==R`.\n\n# Complexity\n- Time complexity: `O(n**4)`\n  - in round one we do `O(n**2)` iterations because we loop over all `wl`, `wl2` combinations and append that order of elements to the queue\n  - then in round two we do iterate over `wl, wl2`, `O(n**2)` things, for each of the `O(n**2)` items in the queue. That\'s `O(n**4)`\n  - however: the most `L` and `R` can be is `O(n)`, each iteration has about half as many elements because about half the people lose\n  - therefore the complexity will look like `O(n**4 + n**4/16 + n**4 / 256 + ...) = O(n**4)`. That\'s because the worst case combinations come from `wl, wl2` both iterating over about half the array size, current n squared over 4, and the current n itself is half of what it used to be\n\n- Space complexity: `O(n**2)` because at worst we have `wl, wl2 ~ O(n)` to start all combinations get pushed to the queue\n\nQuartic scaling is obviously bad. But `n <= 28` is a huge tipoff that we can afford bad scaling and still not get TLE.\n\n# Code\n```\nclass Solution:\n    def earliestAndLatest(self, n: int, firstPlayer: int, secondPlayer: int) -> List[int]:\n        # row, 1..n\n        \n        # in each round i from front competes with i from the back, winner advances. if odd, middle advances\n        # the winner remains in place, such that they\'re ordered by initial position (so numerically 1..n)\n        \n        # firstPlayer, secondPlayer are best, they win against all other players and\n        # we pick who among those two win head-to-head\n\n        # return the first and last possible round they can compete\n\n        # first possible round:\n        #    ....... first ...... second ....\n        #    ABCDEFG                  GFEDCBA\n        #\n        #   each match is basically popFront vs popBack\n        #   then we push the winner to their original side\n        #\n        #   so if we have   L first M second R    then\n        #      if L == R then first and second face off in this current turn\n        #\n        #   otherwise suppose L > R, otherwise flip the array\n        #    R = R + 1 + E, E for "extra"\n        #\n        #    wlog let first be farther from front than second is from back\n\n        #  then we have R   1   (L-1-R) first (N-2*R-2-(L-1-R)-1) second R\n        #                                      N-R-2-L\n        #                         ML                  MR\n\n        # from R vs R: suppose W win on the left. Then we have\n        #               W   x                                     second (R-W)\n        #   if ML < MR: can choose any up to min(ML, MR) to win left\n        #     then first defeats one in MR\n        #     then among the rest we remove half rounded down\n\n        # so let\'s do BFS with a seen set\n        rounds = 1 # current round\n        q = deque()\n        q.append((firstPlayer-1, n-secondPlayer))\n        earliest = n\n        latest = 0\n        while q:\n            seen = set() # seen only needs to have states for the current round and its number of players\n            for _ in range(len(q)):\n                L, R = q.popleft()\n\n                if L == R:\n                    earliest = min(earliest, rounds)\n                    latest = rounds\n                    continue\n                \n                if R > L:\n                    L, R = R, L\n\n                # we have R 1 L-R-1 first n-L-R-2 second R\n                #    R vs R: let WL be number of wins that go to left, in 0..R\n                #\n                # result WL 0 ??????????????????? second (R-WL)\n                \n                ML = L-R-1\n                MR = n-L-R-2\n\n                # really tricky: interior is ML 1/first MR\n                #\n                #    if ML < MR: looks like    ... first .............\n                #             0..ML can be on the left, then first, rest fight AFTER\n                #    if ML > MR: looks like    ............ first ...\n                #           0..MR can be on the right, then ceil((ML-1-MR)/2) ALSO on the left before first\n                #             we\'ll call the ceil(...) extraLeft, the number of winners that will be on the left no matter what\n                #    if ML == MR: looks like .... first ....\n                #           any number on left (same as ML < MR case)\n\n                matches = min(ML, MR)\n                extraLeft = 0 if ML <= MR else (ML-1-MR+1)//2\n\n                lo = min(ML, MR)\n                for wl in range(R+1):\n                    for wl2 in range(matches+1):\n                        newstate = (wl+wl2+extraLeft, R-wl)\n\n                        if newstate in seen: continue\n\n                        seen.add(newstate)\n                        q.append(newstate)\n\n            # prep for next round\n            rounds += 1\n            n -= n//2 # each of the n//2 battles has a loser that gets knocked out\n\n        return [earliest, latest]\n```
['Python3']