How does backtracking with pruning work in the "Maximum Points in an Archery Competition" problem?

Backtracking with pruning helps by exploring all possible arrow distributions, while pruning cuts off branches where Bob cannot beat Alice’s score, thus reducing unnecessary computations.

What role does bit manipulation play in this problem?

Bit manipulation can be used to efficiently manage and track arrow distributions, speeding up the backtracking process and reducing the space complexity.

Can a greedy approach be used to solve the "Maximum Points in an Archery Competition" problem?

Yes, a greedy approach can be helpful in selecting sections where Bob can beat Alice with the fewest arrows, which can optimize the solution by focusing on the most promising sections first.

What are the major pitfalls to avoid in this problem?

Key pitfalls include failing to prune invalid paths early, not considering all edge cases, and misunderstanding how to distribute arrows based on Alice's scores.

How does GhostInterview help with this problem?

GhostInterview provides a structured approach to implementing the backtracking algorithm, optimizes the process using pruning, and guides you through common pitfalls in solving this problem.

#2212

Medium

auto_awesome回溯·pruning

LeetCode 题解工作台

射箭比赛中的最大得分

Alice 和 Bob 是一场射箭比赛中的对手。比赛规则如下： Alice 先射 numArrows 支箭，然后 Bob 也射 numArrows 支箭。分数按下述规则计算：箭靶有若干整数计分区域，范围从 0 到 11 （含 0 和 11 ）。箭靶上每个区域都对应一个得分 k （范围是 0 到…

数组回溯位运算枚举

题目描述

Alice 和 Bob 是一场射箭比赛中的对手。比赛规则如下：

Alice 先射 numArrows 支箭，然后 Bob 也射 numArrows 支箭。
分数按下述规则计算：
1. 箭靶有若干整数计分区域，范围从 0 到 11 （含 0 和 11）。
2. 箭靶上每个区域都对应一个得分 k（范围是 0 到 11），Alice 和 Bob 分别在得分 k 区域射中 a_k 和 b_k 支箭。如果 a_k >= b_k ，那么 Alice 得 k 分。如果 a_k < b_k ，则 Bob 得 k 分
3. 如果 a_k == b_k == 0 ，那么无人得到 k 分。

例如，Alice 和 Bob 都向计分为 11 的区域射 2 支箭，那么 Alice 得 11 分。如果 Alice 向计分为 11 的区域射 0 支箭，但 Bob 向同一个区域射 2 支箭，那么 Bob 得 11 分。

给你整数 numArrows 和一个长度为 12 的整数数组 aliceArrows ，该数组表示 Alice 射中 0 到 11 每个计分区域的箭数量。现在，Bob 想要尽可能 最大化 他所能获得的总分。

返回数组 bobArrows ，该数组表示 Bob 射中 0 到 11 每个计分区域的箭数量。且 bobArrows 的总和应当等于 numArrows 。

如果存在多种方法都可以使 Bob 获得最大总分，返回其中 任意一种 即可。

示例 1：

输入：numArrows = 9, aliceArrows = [1,1,0,1,0,0,2,1,0,1,2,0]
输出：[0,0,0,0,1,1,0,0,1,2,3,1]
解释：上表显示了比赛得分情况。
Bob 获得总分 4 + 5 + 8 + 9 + 10 + 11 = 47 。
可以证明 Bob 无法获得比 47 更高的分数。

示例 2：

输入：numArrows = 3, aliceArrows = [0,0,1,0,0,0,0,0,0,0,0,2]
输出：[0,0,0,0,0,0,0,0,1,1,1,0]
解释：上表显示了比赛得分情况。
Bob 获得总分 8 + 9 + 10 = 27 。
可以证明 Bob 无法获得比 27 更高的分数。

提示：

1 <= numArrows <= 10⁵
aliceArrows.length == bobArrows.length == 12
0 <= aliceArrows[i], bobArrows[i] <= numArrows
sum(aliceArrows[i]) == numArrows

lightbulb

解题思路

方法一：二进制枚举

由于区域数目只有 $12$ 个，因此我们使用二进制枚举的方式，枚举 $\textit{Bob}$ 在哪些区域得分。用一个变量 $\textit{st}$ 表示 $\textit{Bob}$ 获得最大得分的方案，而 $\textit{mx}$ 表示 $\textit{Bob}$ 获得的最大得分。

我们在 $[1, 2^m)$ 的区间内枚举 $\textit{Bob}$ 的得分方案，其中 $m$ 是 $\textit{aliceArrows}$ 的长度。对于每一个方案，我们计算 $\textit{Bob}$ 的得分 $\textit{s}$ 以及射箭的数量 $\textit{cnt}$ 。如果 $\textit{cnt} \leq \textit{numArrows}$ 且 $\textit{s} > \textit{mx}$ ，我们就更新 $\textit{mx}$ 和 $\textit{st}$ 。

然后，我们根据 $\textit{st}$ 计算 $\textit{Bob}$ 的得分方案，如果最后还有剩余的射箭，我们将剩余的射箭分配给第一个区域，即下标为 $0$ 的区域。

时间复杂度 $O(2^m \times m)$ ，其中 $m$ 是 $\textit{aliceArrows}$ 的长度。忽略答案数组的空间消耗，空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

class Solution:
    def maximumBobPoints(self, numArrows: int, aliceArrows: List[int]) -> List[int]:
        st = mx = 0
        m = len(aliceArrows)
        for mask in range(1, 1 << m):
            cnt = s = 0
            for i, x in enumerate(aliceArrows):
                if mask >> i & 1:
                    s += i
                    cnt += x + 1
            if cnt <= numArrows and s > mx:
                mx = s
                st = mask
        ans = [0] * m
        for i, x in enumerate(aliceArrows):
            if st >> i & 1:
                ans[i] = x + 1
                numArrows -= ans[i]
        ans[0] += numArrows
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate suggests using backtracking with pruning to explore different arrow distributions.
question_mark
Candidate attempts to optimize the solution using greedy selection or bit manipulation techniques.
question_mark
Candidate demonstrates an understanding of how pruning reduces unnecessary calculations in this problem.

warning

常见陷阱

外企场景

error
Failing to prune invalid paths early can lead to excessive computation and timeouts.
error
Not considering edge cases where numArrows is small or very large can lead to incorrect solutions.
error
Misunderstanding the problem's goal, such as incorrectly distributing arrows without considering the competition's scoring system.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Alter the number of sections (reduce or increase the size of the aliceArrows array).
arrow_right_alt
Introduce additional constraints on the number of arrows Bob can shoot in each section.
arrow_right_alt
Consider allowing a greater number of arrows or a limit on how many sections Bob must outscore Alice.

help

常见问题

外企场景

继续练习

#2151 基于陈述统计最多好人数 #2044 统计按位或能得到最大值的子集数目 #2397 被列覆盖的最多行数