1900: The-Earliest-and-Latest-Rounds-Where-Players-Compete
Hard

Originally, my solution was to just depth-first search through all the possible rounds (given that the constraints were not too large) and simulate all the possible rounds.

However, there exists a simpler way to phrase the question; for firstPlayer and secondPlayer to play against each other, there has to be an equal number of people to the left of firstPlayer as there is to the right of secondPlayer.

This is intuitive, as we do not really care about the initial positions of characters in the game. For example, given the initial state 1, 2, 3, 4, 5, 6 where firstPlayer = 1 and secondPlayer = 2, realise that after one round, we get:

• 1, 2, 3, where 3 beats 4
• 1, 2, 4, where 4 beats 3

which is logically equivalent. By abstracting away the information of characters initial positions, it reduces the solution space that we need to search and simplifies the algorithm profusely.

If we denote the number of elements left of firstPlayer (including firstPlayer itself) as l, and the number of elements right of secondPlayer (including secondPlayer itself) as r, then, without loss of generality, let us assume that l < r (due to symmetry).

If l == r, then both players must play each other next round, so we can update both the minRound and maxRound if necessary.

Let us also define the total head-count of players per round. If we start with n players,

• if n is odd, then there is gonna exist floor(n/2)+1 = floor((n+1)/2) players in the following round
• if n is even, then there is gonna exist n/2 = floor((n+1)/2)

meaning, whatever happens, we will always have floor((n+1)/2) players in the next round.

Since l < r, all the l players will be facing players to the right of secondPlayer. After playing this round, we know that l will be have to take a value between 1 and l, since either everyone loses (except)firstPlayer or everyone wins or something in between occurs. Thus, we can denote the number of players that win on the left as i.

Then, if i players win on the left side, that implies that at a bare minimum, l - i + 1 players on the right hand side must win (the + 1 is from secondPlayer). If we denote the number of players that win on the right side as j, then we can keep on incrementing j until i+j reaches the minimum value of r or floor((n+1)/2).

Note, using the minimum value of r or floor((n+1)/2) as our limit for i + j make sense; we cannot start with more people that we started with (hence the r) and the sum of i + j must not surpass the amount of players in the next round.

Finally, we also have to check that there are not too many losers (as every round, floor(n/2) players have to lose), so we also have to sum (l-i) + (r-j) and check that it is smaller than or equal to floor(n/2) before recursively running the function for the next round.

Overall, this means we have to search through a smaller solution space and use up less auxiliary space on the stack from recursive calls.

code

class Solution {
public:
    vector<int> earliestAndLatest(int n, int firstPlayer, int secondPlayer) {
        recursion(1, firstPlayer, n-secondPlayer+1, n);
        return {minRound, maxRound};
    }
private:
    int minRound = INT32_MAX;
    int maxRound = 0;
    void recursion(int round, int l, int r, int n) {
        if (l == r) {
            minRound = min(minRound, round);
            maxRound = max(maxRound, round);
            return;
        }

        if (r < l) {
            swap(l, r);
        }

        for (int i = 1; i < l+1; ++i) {
            for (int j = l-i+1; i + j <= min(r, (n+1)/2); ++j) {
                if (l + r - (i + j) <= n / 2) {
                    recursion(round+1, i, j, (n+1)/2);
                }
            }
        }
    }
};

complexity

time taken