The Earliest and Latest Rounds Where Players Compete — LeetCode 1900 Python Solution

HardMemoizationDynamic Programming

Problem: #1900
Pattern: Dynamic Programming
Reading time: 7 min
Source: leetcode.com

The problem

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

Example

Input: n = 11, firstPlayer = 2, secondPlayer = 4
Output: [3,4]
Explanation: One possible scenario which leads to the earliest round number:

Python solution

Python

@cache
def dfs(l: int, r: int, n: int):
    if l + r == n - 1:
        return [1, 1]
    res = [inf, -inf]
    m = n >> 1
    for i in range(1 << m):
        win = [False] * n
        for j in range(m):
            if i >> j & 1:
                win[j] = True
            else:
                win[n - 1 - j] = True
        if n & 1:
            win[m] = True
        win[n - 1 - l] = win[n - 1 - r] = False
        win[l] = win[r] = True
        a = b = c = 0
        for j in range(n):
            if j == l:
                a = c
            if j == r:
                b = c
            if win[j]:
                c += 1
        x, y = dfs(a, b, c)
        res[0] = min(res[0], x + 1)
        res[1] = max(res[1], y + 1)
    return res


class Solution:
    def earliestAndLatest(
        self, n: int, firstPlayer: int, secondPlayer: int
    ) -> List[int]:
        return dfs(firstPlayer - 1, secondPlayer - 1, n)

Complexity

Measure	Complexity
Time	O(n·m) (typical)
Space	O(n·m) or optimized auxiliary

Pattern: Dynamic Programming

Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 1900. The Earliest and Latest Rounds Where Players Compete is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Dynamic Programming and Memoization.

The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1900. The Earliest and Latest Rounds Where Players Compete?: LeetCode 1900. The Earliest and Latest Rounds Where Players Compete is rated Hard on LeetCode.
What topics does LeetCode 1900. The Earliest and Latest Rounds Where Players Compete cover?: LeetCode 1900. The Earliest and Latest Rounds Where Players Compete is tagged Memoization and Dynamic Programming on LeetCode.