<p>There is a tournament where <code>n</code> players are participating. The players are standing in a single row and are numbered from <code>1</code> to <code>n</code> based on their <strong>initial</strong> standing position (player <code>1</code> is the first player in the row, player <code>2</code> is the second player in the row, etc.).</p>

<p>The tournament consists of multiple rounds (starting from round number <code>1</code>). In each round, the <code>i<sup>th</sup></code> player from the front of the row competes against the <code>i<sup>th</sup></code> player from the end of the row, and the winner advances to the next round. When the number of players is odd for the current round, the player in the middle automatically advances to the next round.</p>

<ul>
	<li>For example, if the row consists of players <code>1, 2, 4, 6, 7</code>

	<ul>
		<li>Player <code>1</code> competes against player <code>7</code>.</li>
		<li>Player <code>2</code> competes against player <code>6</code>.</li>
		<li>Player <code>4</code> automatically advances to the next round.</li>
	</ul>
	</li>
</ul>

<p>After each round is over, the winners are lined back up in the row based on the <strong>original ordering</strong> assigned to them initially (ascending order).</p>

<p>The players numbered <code>firstPlayer</code> and <code>secondPlayer</code> are the best in the tournament. They can win against any other player before they compete against each other. If any two other players compete against each other, either of them might win, and thus you may <strong>choose</strong> the outcome of this round.</p>

<p>Given the integers <code>n</code>, <code>firstPlayer</code>, and <code>secondPlayer</code>, return <em>an integer array containing two values, the <strong>earliest</strong> possible round number and the&nbsp;<strong>latest</strong> possible round number in which these two players will compete against each other, respectively</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 11, firstPlayer = 2, secondPlayer = 4
<strong>Output:</strong> [3,4]
<strong>Explanation:</strong>
One possible scenario which leads to the earliest round number:
First round: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
Second round: 2, 3, 4, 5, 6, 11
Third round: 2, 3, 4
One possible scenario which leads to the latest round number:
First round: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
Second round: 1, 2, 3, 4, 5, 6
Third round: 1, 2, 4
Fourth round: 2, 4
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 5, firstPlayer = 1, secondPlayer = 5
<strong>Output:</strong> [1,1]
<strong>Explanation:</strong> The players numbered 1 and 5 compete in the first round.
There is no way to make them compete in any other round.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>2 &lt;= n &lt;= 28</code></li>
	<li><code>1 &lt;= firstPlayer &lt; secondPlayer &lt;= n</code></li>
</ul>

class Solution:
    def earliestAndLatest(self, n: int, firstPlayer: int, secondPlayer: int) -> List[int]:
        # row, 1..n
        
        # in each round i from front competes with i from the back, winner advances. if odd, middle advances
        # the winner remains in place, such that they're ordered by initial position (so numerically 1..n)
        
        # firstPlayer, secondPlayer are best, they win against all other players and
        # we pick who among those two win head-to-head

        # return the first and last possible round they can compete

        # first possible round:
        #    ....... first ...... second ....
        #    ABCDEFG                  GFEDCBA
        #
        #   each match is basically popFront vs popBack
        #   then we push the winner to their original side
        #
        #   so if we have   L first M second R    then
        #      if L == R then first and second face off in this current turn
        #
        #   otherwise suppose L > R, otherwise flip the array
        #    R = R + 1 + E, E for "extra"
        #
        #    wlog let first be farther from front than second is from back

        #  then we have R   1   (L-1-R) first (N-2*R-2-(L-1-R)-1) second R
        #                                      N-R-2-L
        #                         ML                  MR

        # from R vs R: suppose W win on the left. Then we have
        #               W   x                                     second (R-W)
        #   if ML < MR: can choose any up to min(ML, MR) to win left
        #     then first defeats one in MR
        #     then among the rest we remove half rounded down

        # so let's do BFS with a seen set
        rounds = 1 # current round
        q = deque()
        q.append((firstPlayer-1, n-secondPlayer))
        earliest = n
        latest = 0
        while q:
            seen = set() # seen only needs to have states for the current round and its number of players
            for _ in range(len(q)):
                L, R = q.popleft()

                if L == R:
                    earliest = min(earliest, rounds)
                    latest = rounds
                    continue
                
                if R > L:
                    L, R = R, L

                # we have R 1 L-R-1 first n-L-R-2 second R
                #    R vs R: let WL be number of wins that go to left, in 0..R
                #
                # result WL 0 ??????????????????? second (R-WL)
                
                ML = L-R-1
                MR = n-L-R-2

                # really tricky: interior is ML 1/first MR
                #
                #    if ML < MR: looks like    ... first .............
                #             0..ML can be on the left, then first, rest fight AFTER
                #    if ML > MR: looks like    ............ first ...
                #           0..MR can be on the right, then ceil((ML-1-MR)/2) ALSO on the left before first
                #             we'll call the ceil(...) extraLeft, the number of winners that will be on the left no matter what
                #    if ML == MR: looks like .... first ....
                #           any number on left (same as ML < MR case)

                matches = min(ML, MR)
                extraLeft = 0 if ML <= MR else (ML-1-MR+1)//2

                lo = min(ML, MR)
                for wl in range(R+1):
                    for wl2 in range(matches+1):
                        newstate = (wl+wl2+extraLeft, R-wl)

                        if newstate in seen: continue

                        seen.add(newstate)
                        q.append(newstate)

            # prep for next round
            rounds += 1
            n -= n//2 # each of the n//2 battles has a loser that gets knocked out

        return [earliest, latest]
16500