[Python] BFS + bit mask
The idea is simple: encoding the player state using bit array, then generate competing pairs, and based on the pairs, we can generate the next state. \n\n## Exa
The idea is simple: encoding the player state using bit array, then generate competing pairs, and based on the pairs, we can generate the next state. \n\n## Example\nLet\'s say we have 5 players, then the initial bit array would be `[1, 1, 1, 1, 1]`. We can generate pairs using the rules stated in the question, so we have: `[(0, 4), (1, 3), (2, 2)]`, means player 0 is fighting against player 4, player 1 is against player 3, and player 2 is against no one (0-index here).  *(This is the pair generation part)*\n\nIf we say the `firstPlayer == 0` and `secondPlayer == 2` (0-indexed), then we have the bit array [**1**, 1, **1**, 1, 1]. Because the two players can beat any one except one another, so we don\'t have to generate pairs for them, unless they are competing with each other. Thus, we *actually* have pairs like `[(0, 0), (1, 3), (2, 2)]`. *(This is the amendment for pair generation part)*\n\nAs the first and last matches are determined (0 always win, 2 is competing with no one), so the possible outcomes are `[0, 1, 2]` and `[0, 3, 2]`. Then we convert this information back to bit array, then we have `[1, 1, 1, 0, 0]` and `[1, 0, 1, 1, 0]`. *(This is the state generation part)*\n\nWe can then move on from those two cases until we have tried all possible states.\n\n## Code\n```python\nclass Solution:\n    def earliestAndLatest(self, n: int, firstPlayer: int, secondPlayer: int) -> List[int]:\n        firstPlayer -= 1\n        secondPlayer -= 1\n        def competingPlayers(state): # generate player pairs from bit array `state`\n            first = 0\n            last = n - 1\n            players = []\n            found = False\n            while first <= last:\n                while first <= last and state & (1 << first) == 0:\n                    first += 1\n                while last >= first and state & (1 << last) == 0:\n                    last -= 1\n                if first > last: break\n                if first == firstPlayer and last == secondPlayer:\n                    players.append((first, last))\n                    found = True\n                elif first == firstPlayer or first == secondPlayer:\n                    players.append((first, first))\n                elif last == firstPlayer or last == secondPlayer:\n                    players.append((last, last))\n                else:\n                    players.append((first, last))\n                first += 1\n                last -= 1\n            return players, found\n        \n        def states(players, i): # generate bit array from player\n            if i >= len(players): return [0]\n            suffices = states(players, i + 1)\n            prefix = 1 << players[i][0]\n            combined = [prefix | suffix for suffix in suffices]\n            if players[i][1] != players[i][0]:\n                prefix = 1 << players[i][1]\n                combined.extend(prefix | suffix for suffix in suffices)\n            return combined\n        \n        from collections import deque\n        visited = {(1 << n) - 1}\n        queue = deque(visited)\n        steps = 1\n        minSteps = n + 1\n        maxSteps = -1\n        while queue:\n            for _ in range(len(queue)):\n                state = queue.popleft()\n                players, end = competingPlayers(state)\n                if end:\n                    minSteps = min(minSteps, steps)\n                    maxSteps = max(maxSteps, steps)\n                else:\n                    for state in states(players, 0):\n                        if state in visited: continue\n                        visited.add(state)\n                        queue.append(state)\n            steps += 1\n        return [minSteps, maxSteps]\n```
[]