How does dynamic programming help in solving the Earliest and Latest Rounds Where Players Compete problem?

Dynamic programming allows for efficient simulation of the rounds by breaking down the problem into smaller subproblems and solving each one, saving time by avoiding redundant computations.

What is bitmasking and how does it apply to this problem?

Bitmasking is a technique used to represent sets of players. Each bit in a bitmask indicates whether a player is still in the game. This technique is crucial for efficiently tracking the progression of players through each round.

How can I efficiently simulate the rounds in this problem?

By using bitmasks to represent the set of players in each round, you can simulate the rounds and track which players advance, allowing you to determine when the two players meet.

What is memoization and why is it important for this problem?

Memoization stores the results of subproblems to avoid redundant calculations. In this problem, it helps optimize the simulation of rounds by storing previously computed matchups, leading to faster execution.

What is the time complexity of solving the Earliest and Latest Rounds Where Players Compete problem?

The time complexity is O(n^4 log n), which comes from simulating multiple rounds with bitmasking and state transitions. The memoization technique helps to manage the large number of possible states.

#1900

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

最佳运动员的比拼回合

n 名运动员参与一场锦标赛，所有运动员站成一排，并根据最开始的站位从 1 到 n 编号（运动员 1 是这一排中的第一个运动员，运动员 2 是第二个运动员，依此类推）。锦标赛由多个回合组成（从回合 1 开始）。每一回合中，这一排从前往后数的第 i 名运动员需要与从后往前数的第 i 名运动员比拼，…

动态规划记忆化

题目描述

n 名运动员参与一场锦标赛，所有运动员站成一排，并根据 最开始的 站位从 1 到 n 编号（运动员 1 是这一排中的第一个运动员，运动员 2 是第二个运动员，依此类推）。

锦标赛由多个回合组成（从回合 1 开始）。每一回合中，这一排从前往后数的第 i 名运动员需要与从后往前数的第 i 名运动员比拼，获胜者将会进入下一回合。如果当前回合中运动员数目为奇数，那么中间那位运动员将轮空晋级下一回合。

例如，当前回合中，运动员 1, 2, 4, 6, 7 站成一排
- 运动员 1 需要和运动员 7 比拼
- 运动员 2 需要和运动员 6 比拼
- 运动员 4 轮空晋级下一回合

每回合结束后，获胜者将会基于最开始分配给他们的原始顺序（升序）重新排成一排。

编号为 firstPlayer 和 secondPlayer 的运动员是本场锦标赛中的最佳运动员。在他们开始比拼之前，完全可以战胜任何其他运动员。而任意两个其他运动员进行比拼时，其中任意一个都有获胜的可能，因此你可以裁定谁是这一回合的获胜者。

给你三个整数 n、firstPlayer 和 secondPlayer 。返回一个由两个值组成的整数数组，分别表示两位最佳运动员在本场锦标赛中比拼的最早回合数和最晚回合数。

示例 1：

输入：n = 11, firstPlayer = 2, secondPlayer = 4
输出：[3,4]
解释：
一种能够产生最早回合数的情景是：
回合 1：1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
回合 2：2, 3, 4, 5, 6, 11
回合 3：2, 3, 4
一种能够产生最晚回合数的情景是：
回合 1：1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
回合 2：1, 2, 3, 4, 5, 6
回合 3：1, 2, 4
回合 4：2, 4

示例 2：

输入：n = 5, firstPlayer = 1, secondPlayer = 5
输出：[1,1]
解释：两名最佳运动员 1 和 5 将会在回合 1 进行比拼。
不存在使他们在其他回合进行比拼的可能。

提示：

2 <= n <= 28
1 <= firstPlayer < secondPlayer <= n

lightbulb

解题思路

方法一：记忆化搜索 + 二进制枚举

我们定义一个函数 $\text{dfs}(l, r, n)$ ，表示在当前回合中，编号为 $l$ 和 $r$ 的运动员在 $n$ 名运动员中比拼的最早和最晚回合数。

函数 $\text{dfs}(l, r, n)$ 的执行逻辑如下：

如果 $l + r = n - 1$ ，说明两名运动员在当前回合中比拼，返回 $[1, 1]$ 。
如果 $f[l][r][n] \neq 0$ ，说明之前已经计算过这个状态，直接返回结果。
初始化最早回合数为正无穷大，最晚回合数为负无穷大。
计算当前回合中前半部分的运动员数目 $m = n / 2$ 。
枚举前半部分的所有可能的胜者组合（使用二进制枚举），对于每一种组合：
- 根据当前组合确定哪些运动员获胜。
- 确定当前回合中编号为 $l$ 和 $r$ 的运动员在当前回合中的位置。
- 统计当前回合中编号为 $l$ 和 $r$ 的运动员在剩余运动员中的位置，记为 $a$ 和 $b$ ，以及剩余运动员的总数 $c$ 。
- 递归调用 $\text{dfs}(a, b, c)$ ，获取当前状态的最早和最晚回合数。
- 更新最早回合数和最晚回合数。
将计算结果存储在 $f[l][r][n]$ 中，并返回最早和最晚回合数。

答案为 $\text{dfs}(\text{firstPlayer} - 1, \text{secondPlayer} - 1, n)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

@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)

speed

复杂度分析

指标	值
时间	O(n^4 \log n)
空间	O(n^2 \log n)

psychology

面试官常问的追问

外企场景

question_mark
Strong understanding of dynamic programming and state transitions is required.
question_mark
Ability to apply memoization to optimize the solution and avoid recalculating results.
question_mark
Comfortable with bitmasking and simulating multiple rounds efficiently.

warning

常见陷阱

外企场景

error
Misunderstanding how to simulate the rounds efficiently with dynamic programming.
error
Failing to memoize intermediate results, leading to unnecessary recalculations.
error
Overcomplicating the solution when a brute force bitmasking approach can be applied.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Implementing the solution without dynamic programming for simplicity, which may lead to high time complexity.
arrow_right_alt
Solving the problem using a simulation-based approach without bitmasking.
arrow_right_alt
Optimizing the solution by considering fewer rounds or limiting unnecessary simulation steps.

help

常见问题

外企场景

继续练习

#1857 有向图中最大颜色值 #1815 得到新鲜甜甜圈的最多组数 #2019 解出数学表达式的学生分数