Maximum Points in an Archery Competition - Video Solutions
2212. Maximum Points in an Archery Competition || Leetcode Weekly Contest 285 || Leetcode 2212
Maximum Points in an Archery Competition - Video Solution
Watch 10 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,911 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
Alice and Bob are opponents in an archery competition. The competition has set the following rules:
- Alice first shoots
numArrowsarrows and then Bob shootsnumArrowsarrows. - The points are then calculated as follows:
- The target has integer scoring sections ranging from
0to11inclusive. - For each section of the target with score
k(in between0to11), say Alice and Bob have shotakandbkarrows on that section respectively. Ifak >= bk, then Alice takeskpoints. Ifak < bk, then Bob takeskpoints. - However, if
ak == bk == 0, then nobody takeskpoints.
- The target has integer scoring sections ranging from
-
For example, if Alice and Bob both shot
2arrows on the section with score11, then Alice takes11points. On the other hand, if Alice shot0arrows on the section with score11and Bob shot2arrows on that same section, then Bob takes11points.
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]) == numArrows
Approach Overview
Problem 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.
Complexity Analysis
| 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. |