Problem statement

https://leetcode.com/problems/the-earliest-and-latest-rounds-where-players-compete/

Solution

Not very difficult problem, the main problem in python to make it work without TLE. Let us use dfs(pos, i) function, where:

  1. pos is tuple of players we still have.
  2. i is how many matches were already played.

Each time we run recursion, check that pair (firstPlayer, secondPlayer) is not here yet (denoted by F and S), if it is, add number of matches played to set ans and return. Also, ignore pairs where one of the two players is S or F. Finally, use functionality of python product function to fastly generate all next positions.

Complexity

We have n players in the beginning, and we have n//2 pairs, so there is O(2^(n//2)) options for the first step, then it will be O(2^(n//4)) and so on, so in the end we can have potentially O(2^n) positions, which is our time complexity. However, due to careful prunning, it practice it is much less, like if we have 28, then on the next step we have not 2^14, but 2^12 positions, because S and F always go to the next match or we stop, then we have 2^5 and then we have 2^1, so it is more like 2^(12 + 5 + 1) = 2^18, so it is still feasible. Space complexity is O(n).

Code

class Solution:
    def earliestAndLatest(self, n, F, S):
        ans = set()
        def dfs(pos, i):
            M, pairs = len(pos), []
            if M < 2: return

            for j in range(M//2):
                a, b = pos[j], pos[-1-j]
                if (a, b) == (F, S):
                    ans.add(i)
                    return
                if a != F and b != F and a != S and b != S:
                    pairs.append((a, b))

            addon = (F, S) if M%2 == 0 else tuple(set([F, S, pos[M//2]]))
            for elem in product(*pairs):
                dfs(sorted(elem + addon), i + 1)

        dfs(list(range(1, n+1)), 1)
        return [min(ans), max(ans)]

Solution 2

This solution is borrowed from https://leetcode.com/problems/the-earliest-and-latest-rounds-where-players-compete/discuss/1268560/Python-simple-top-down-dp-solution-O(N4*logN), here I just rewrote it a bit and try to add some explanations with examples. Please go and upvote this post, it deserves more upvotes.

Define by dp(l, r, m, q) state with the following parameters:

  1. l and r are positions of our F and S players from start and from end. For example if we have 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, where we denoted by bold elements the first and the second player, and we have l = 3 and r = 6.
  2. m is current number of players, we have 12 here and q is number of games already played.

What can happen on the next step? Let us go through options and see what is going on. Let us denote by underline x the players who loose and by x player who win. Then at the moment we have the following situation:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12.

What can happen that among players 1 and 2 there can be zero, one or two wins, and actually it does not matter which ones. Let us consider the cases:

  1. We have zero wins, so we have 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12. Then what we know for sure is in new round player 3 will be the first. Player 7 can be either 3, 4 or 5 from the end.
  2. We have one wins, so we have 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12. Then what we know for sure is in new round player 3 will be the second. Player 7 can be either 2, 3 or 4 from the end.
  3. We have two wins, so we have 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12. Then what we know for sure is in new round player 3 will be the third. Player 7 can be either 1, 2 or 3 from the end.

So, what we need to do is to carefully understand all the cases we can meet.

Complexity

We have O(n^2*log(n) states: O(n) for both l and r and log(n) states for m, which will define q in unique way. We have O(n^2) transactions from one state to others, so time complexity is O(n^4*log n), space complexity is O(n^2*log n). Actually, more detailed analysis shows that log factor can be removed, because say n = 64, then we have O(64*64) states for m = 64, then we have O(32*32) states for m = 32 and so on. So final time complexity is O(n^4), space is O(n^2).

Code

class Solution:
    def earliestAndLatest(self, n, F, S):
        @lru_cache(None)
        def dp(l, r, m, q):
            if l > r:  dp(r, l, m, q)
            if l == r: ans.add(q)
            
            for i in range(1, l + 1):
                for j in range(l-i+1, r-i+1):
                    if not (m+1)//2 >= i + j >= l + r - m//2: continue
                    dp(i, j, (m + 1) // 2, q + 1)
        
        ans = set()
        dp(F, n - S + 1, n, 1)
        return [min(ans), max(ans)]