Watch 9 video solutions for Maximum Points in an Archery Competition, a medium level problem involving Array, Backtracking, Bit Manipulation. This walkthrough by Bro Coders has 2,890 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Alice and Bob are opponents in an archery competition. The competition has set the following rules:
numArrows arrows and then Bob shoots numArrows arrows.0 to 11 inclusive.k (in between 0 to 11), say Alice and Bob have shot ak and bk arrows on that section respectively. If ak >= bk, then Alice takes k points. If ak < bk, then Bob takes k points.ak == bk == 0, then nobody takes k points.For example, if Alice and Bob both shot 2 arrows on the section with score 11, then Alice takes 11 points. On the other hand, if Alice shot 0 arrows on the section with score 11 and Bob shot 2 arrows on that same section, then Bob takes 11 points.
You are given the integer numArrows and an integer array aliceArrows of size 12, which represents the number of arrows Alice shot on each scoring section from 0 to 11. Now, Bob wants to maximize the total number of points he can obtain.
Return the array bobArrows which represents the number of arrows Bob shot on each scoring section from 0 to 11. The sum of the values in bobArrows should equal numArrows.
If there are multiple ways for Bob to earn the maximum total points, return any one of them.
Example 1:
Input: numArrows = 9, aliceArrows = [1,1,0,1,0,0,2,1,0,1,2,0] Output: [0,0,0,0,1,1,0,0,1,2,3,1] Explanation: The table above shows how the competition is scored. Bob earns a total point of 4 + 5 + 8 + 9 + 10 + 11 = 47. It can be shown that Bob cannot obtain a score higher than 47 points.
Example 2:
Input: numArrows = 3, aliceArrows = [0,0,1,0,0,0,0,0,0,0,0,2] Output: [0,0,0,0,0,0,0,0,1,1,1,0] Explanation: The table above shows how the competition is scored. Bob earns a total point of 8 + 9 + 10 = 27. It can be shown that Bob cannot obtain a score higher than 27 points.
Constraints:
1 <= numArrows <= 105aliceArrows.length == bobArrows.length == 120 <= aliceArrows[i], bobArrows[i] <= numArrowssum(aliceArrows[i]) == numArrowsProblem Overview: Bob and Alice shoot arrows at 12 scoring sections (0–11). Alice’s arrow counts are known. Bob has numArrows and earns i points only if he shoots aliceArrows[i] + 1 arrows in section i. The task is to distribute Bob’s arrows to maximize total points and return the arrow allocation.
Approach 1: Greedy Subset Enumeration (Bitmask) (Time: O(2^12), Space: O(1))
There are only 12 scoring sections, which makes full enumeration feasible. Treat each section as a binary decision: either Bob wins it by spending aliceArrows[i] + 1 arrows or skips it. Use a bitmask from 0 to 2^12 - 1 to represent every subset of sections Bob tries to win. For each mask, iterate through the bits, compute arrows required, and accumulate the score if the cost fits within numArrows. Track the configuration with the highest score and assign remaining arrows to section 0. This works well because the search space is tiny (4096 states). The method relies heavily on Bit Manipulation and simple iteration over an Array.
Approach 2: Dynamic Programming (0/1 Knapsack) (Time: O(12 * numArrows), Space: O(12 * numArrows))
This problem maps directly to a 0/1 knapsack formulation. Each section i is an item with value i (points gained) and weight aliceArrows[i] + 1 (arrows required to win). Build a DP table where dp[i][j] represents the maximum points achievable using the first i sections with j arrows. For each section, decide whether to skip it or spend the required arrows to win it. After filling the table, backtrack through the decisions to reconstruct Bob’s arrow distribution. This approach demonstrates classic Dynamic Programming thinking and generalizes well when the number of sections grows.
Recommended for interviews: Subset enumeration using bitmasks is typically the fastest to implement because the state space is fixed at 2^12. It clearly shows you recognized the constraint that makes brute force viable. The DP approach demonstrates stronger algorithmic modeling by converting the scoring system into a knapsack problem, which interviewers often appreciate for its clarity and scalability.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Subset Enumeration (Bitmask) | O(2^12) | O(1) | Best when the number of scoring sections is small and fixed. Fast to implement and easy to reason about. |
| Dynamic Programming (0/1 Knapsack) | O(12 * numArrows) | O(12 * numArrows) | Useful when modeling the problem formally as a resource allocation problem or when the number of sections could scale. |