Maximum Points in an Archery Competition
MedPrompt
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
Approaches
3 approaches with complexity analysis and trade-offs.
This approach models the problem as a classic 0/1 Knapsack problem. Each scoring section k (from 1 to 11) is an item. The "weight" of the item is the number of arrows Bob needs to win that section (aliceArrows[k] + 1), and the "value" is the score k. Bob's numArrows is the knapsack's capacity. The goal is to select a set of items (sections) to maximize the total value (score) without exceeding the knapsack's capacity (total arrows).
Algorithm
- Model the problem as a 0/1 Knapsack problem where sections are items, arrows are weight, and points are value.
- Create a 2D DP table
dp[i][j]to store the maximum score using sectionsito11withjarrows. - The table size will be
(12 + 1) x (numArrows + 1). - Fill the table iteratively from
i = 11down to0andj = 0tonumArrows. - The recurrence relation for
dp[i][j]ismax(score_if_concede, score_if_win):score_if_concede = dp[i+1][j]score_if_win = i + dp[i+1][j - (aliceArrows[i] + 1)](ifjis sufficient).
- The maximum possible score is
dp[0][numArrows]. - Reconstruct the
bobArrowsarray by tracing back the decisions made in the DP table that led to the optimal score. - Start with
arrowsLeft = numArrowsand iterate fromi = 0to11. - At each section
i, check if winning the section (i + dp[i+1][arrowsLeft - cost]) was better than conceding (dp[i+1][arrowsLeft]). - Based on the check, set
bobArrows[i]and updatearrowsLeft. - Allocate any remaining arrows to
bobArrows[0].
Walkthrough
We use a 2D DP table, dp[i][j], to store the maximum score achievable by considering sections from i down to 0 with j arrows.
The state transition is defined as follows: For each section i and for each possible number of arrows j, Bob has two choices:
- Concede section
i: Bob uses 0 arrows for this section. The score is determined by the optimal strategy for the remaining sections and arrows, which isdp[i+1][j]. - Win section
i: Bob usescost = aliceArrows[i] + 1arrows. This is only possible ifj >= cost. The score would bei + dp[i+1][j - cost]. Thedp[i][j]value is the maximum of the outcomes of these two choices. The table is filled starting from the last section (11) down to the first (0). The final maximum score isdp[0][numArrows]. After computing the entire DP table, we reconstruct thebobArrowsarray by backtracking through the table, starting fromdp[0][numArrows], to determine which choice (win or concede) was made for each section to achieve the maximum score. Any arrows remaining after allocating for the winning sections are placed inbobArrows[0].
class Solution { public int[] maximumBobPoints(int numArrows, int[] aliceArrows) { int n = 12; // dp[i][j] = max score using sections i..11 with j arrows int[][] dp = new int[n + 1][numArrows + 1]; for (int i = n - 1; i >= 0; i--) { for (int j = 0; j <= numArrows; j++) { // Option 1: Concede section i int concedeScore = dp[i + 1][j]; // Option 2: Win section i int winScore = 0; int arrowsNeeded = aliceArrows[i] + 1; if (j >= arrowsNeeded) { winScore = i + dp[i + 1][j - arrowsNeeded]; } dp[i][j] = Math.max(concedeScore, winScore); } } int[] bobArrows = new int[n]; int arrowsLeft = numArrows; // Reconstruct the path from the DP table for (int i = 0; i < n; i++) { int arrowsNeeded = aliceArrows[i] + 1; int concedeScore = dp[i + 1][arrowsLeft]; int winScore = 0; if (arrowsLeft >= arrowsNeeded) { winScore = i + dp[i + 1][arrowsLeft - arrowsNeeded]; } if (winScore > concedeScore) { bobArrows[i] = arrowsNeeded; arrowsLeft -= arrowsNeeded; } else { bobArrows[i] = 0; } } bobArrows[0] += arrowsLeft; return bobArrows; }}Complexity
Time
O(N * W), where N is the number of sections (12) and W is `numArrows`. The complexity is dominated by filling the DP table, which has `N * W` states.
Space
O(N * W) to store the DP table required for reconstructing the solution path, where N=12 and W=`numArrows`.
Trade-offs
Pros
A standard technique for optimization problems like Knapsack.
Guarantees finding the optimal solution.
Would be efficient if the number of arrows was small and the number of sections was large.
Cons
Slower than brute-force approaches for the given constraints due to the large potential value of
numArrows.Requires significant memory (
O(N * W)) for the DP table, which can be an issue ifnumArrowsis very large.
Since the number of scoring sections is small (12), we can explore every possible combination of sections Bob could win. This approach uses a bitmask, an integer, to represent each of the 2^12 possible subsets of sections. Each bit in the mask corresponds to a section, and if the bit is set, it means Bob attempts to win that section.
Algorithm
- Initialize
maxScore = -1andbestBobArrowsto an empty or default array. - Loop a variable
maskfrom0to(1 << 12) - 1. - Inside the loop, for each
mask:- Initialize
currentScore = 0,arrowsUsed = 0, and a temporarycurrentBobArrowsarray. - Loop
jfrom 0 to 11. - If the
j-th bit ofmaskis 1, it signifies winning sectionj. UpdatecurrentScore,arrowsUsed, andcurrentBobArrows[j]. - After the inner loop, check if
arrowsUsed <= numArrows. - If it is a valid combination, and if
currentScore > maxScore, updatemaxScoreandbestBobArrows. Remember to add the remaining arrows (numArrows - arrowsUsed) tobestBobArrows[0].
- Initialize
- After iterating through all masks, return
bestBobArrows.
Walkthrough
We iterate through all integers from 0 to 2^12 - 1. Each integer acts as a bitmask.
For each mask, we determine the subset of sections Bob will try to win. The j-th bit being 1 means Bob wins section j.
We calculate the total arrows required for this combination by summing aliceArrows[j] + 1 for all chosen sections j.
We also calculate the total score by summing j for all chosen sections.
If the total arrows required do not exceed numArrows, this is a valid strategy.
We keep track of the maximum score seen so far and the corresponding arrow distribution. If the current strategy yields a higher score, we update our best solution.
After checking all 2^12 masks, the stored best solution is the answer. Any leftover arrows are assigned to bobArrows[0].
class Solution { public int[] maximumBobPoints(int numArrows, int[] aliceArrows) { int n = 12; int maxScore = -1; int[] bestBobArrows = new int[n]; // Iterate through all 2^12 subsets of sections {0, ..., 11} for (int mask = 0; mask < (1 << n); mask++) { int currentScore = 0; int arrowsUsed = 0; int[] currentBobArrows = new int[n]; for (int j = 0; j < n; j++) { // Check if j-th bit is set, meaning Bob wins section j if (((mask >> j) & 1) == 1) { int cost = aliceArrows[j] + 1; arrowsUsed += cost; currentBobArrows[j] = cost; currentScore += j; } } if (arrowsUsed <= numArrows) { if (currentScore > maxScore) { maxScore = currentScore; // Distribute remaining arrows to any section (e.g., 0) currentBobArrows[0] += (numArrows - arrowsUsed); bestBobArrows = currentBobArrows; } } } return bestBobArrows; }}Complexity
Time
O(N * 2^N), where N is 12. We iterate through `2^N` masks, and for each, we perform an O(N) loop to calculate score and arrow cost.
Space
O(N) to store the arrow distributions for the current and best solutions, where N=12.
Trade-offs
Pros
Faster than the DP approach for the given constraints.
Implementation is straightforward and non-recursive, avoiding stack depth issues.
Cons
Time complexity is exponential in the number of sections, making it infeasible for a larger number of sections.
This approach is conceptually similar to bitmasking, as it also explores all possible combinations of sections to win. However, it uses recursion to build the solutions. We define a recursive function that makes a decision for one section at a time and then calls itself for the next section.
Algorithm
- Define a recursive helper function
backtrack(index, arrowsLeft, currentBobArrows, currentScore). - Use global variables
maxScoreandbestBobArrowsto keep track of the best solution found. - The initial call is
backtrack(11, numArrows, new int[12], 0). - In the
backtrackfunction:- Base Case: If
index < 0, all decisions are made. ComparecurrentScorewithmaxScoreand update the global best solution if necessary. AddarrowsLeftto the[0]index of the solution. - Recursive Step:
- Explore the path of winning section
index: IfarrowsLeftis sufficient, updatecurrentBobArrows,arrowsLeft,currentScore, and make a recursive call forindex - 1. After the call returns, revert the changes tocurrentBobArrows(this is the "backtracking" step). - Explore the path of conceding section
index: Make a recursive call forindex - 1without changing the state.
- Explore the path of winning section
- Base Case: If
Walkthrough
We design a recursive function, say backtrack(index, arrowsLeft, currentBobArrows, currentScore).
The function considers decisions for sections from 11 down to 0.
At each index, there are two recursive paths:
- Win section
index: IfarrowsLeftis sufficient to usealiceArrows[index] + 1arrows, we make this choice. We updatecurrentBobArrows, decrementarrowsLeft, addindextocurrentScore, and recurse forindex - 1. - Concede section
index: We use 0 arrows for this section and recurse forindex - 1with unchangedarrowsLeftandcurrentScore. The base case for the recursion is whenindex < 0, meaning decisions have been made for all sections. At this point, we check if thecurrentScoreis the best we've seen. If so, we update our globalmaxScoreandbestBobArrowssolution. AnyarrowsLeftare added tobestBobArrows[0]. To avoid carrying state changes between different recursive branches, we must "backtrack" after a recursive call returns, by undoing the changes made tocurrentBobArrows.
class Solution { int maxScore = -1; int[] bestBobArrows = null; int numArrows; int[] aliceArrows; public int[] maximumBobPoints(int numArrows, int[] aliceArrows) { this.numArrows = numArrows; this.aliceArrows = aliceArrows; backtrack(11, numArrows, new int[12], 0); if (bestBobArrows == null) { // Default case if no sections are won bestBobArrows = new int[12]; bestBobArrows[0] = numArrows; } return bestBobArrows; } private void backtrack(int index, int arrowsLeft, int[] currentBobArrows, int currentScore) { if (index < 0) { if (currentScore > maxScore) { maxScore = currentScore; bestBobArrows = currentBobArrows.clone(); bestBobArrows[0] += arrowsLeft; } return; } // Option 1: Win section 'index' int arrowsToWin = aliceArrows[index] + 1; if (arrowsLeft >= arrowsToWin) { currentBobArrows[index] = arrowsToWin; backtrack(index - 1, arrowsLeft - arrowsToWin, currentBobArrows, currentScore + index); currentBobArrows[index] = 0; // Backtrack } // Option 2: Concede section 'index' backtrack(index - 1, arrowsLeft, currentBobArrows, currentScore); }}Complexity
Time
O(2^N), where N is 12. The recursion tree has `2^N` leaves, and the total number of nodes is approximately `2^(N+1)`.
Space
O(N) for the recursion stack depth, where N=12.
Trade-offs
Pros
The most efficient approach for the given constraints.
The logic directly maps to the decision-making process (win or concede for each section).
Cons
Its exponential time complexity makes it unsuitable for problems with a larger number of choices.
Recursive solutions can lead to stack overflow errors if the recursion depth is very large (not an issue here).
Solutions
Solution
class Solution {public int[] maximumBobPoints(int numArrows, int[] aliceArrows) { int n = aliceArrows.length; int mx = -1; int state = 0; for (int mask = 1; mask < 1 << n; ++mask) { int cnt = 0, points = 0; for (int i = 0; i < n; ++i) { if (((mask >> i) & 1) == 1) { cnt += aliceArrows[i] + 1; points += i; } } if (cnt <= numArrows && mx < points) { state = mask; mx = points; } } int[] ans = new int[n]; for (int i = 0; i < n; ++i) { if (((state >> i) & 1) == 1) { ans[i] = aliceArrows[i] + 1; numArrows -= ans[i]; } } ans[0] += numArrows; return ans; }}/** * @param {number} numArrows * @param {number[]} aliceArrows * @return {number[]} */ var maximumBobPoints = function (numArrows, aliceArrows) { let [st, mx] = [0, 0]; const m = aliceArrows.length; for (let mask = 1; mask < 1 << m; mask++) { let [cnt, s] = [0, 0]; for (let i = 0; i < m; i++) { if ((mask >> i) & 1) { cnt += aliceArrows[i] + 1; s += i; } } if (cnt <= numArrows && s > mx) { mx = s; st = mask; } } const ans = Array(m).fill(0); for (let i = 0; i < m; i++) { if ((st >> i) & 1) { ans[i] = aliceArrows[i] + 1; numArrows -= ans[i]; } } ans[0] += numArrows; return ans; };class Solution {public: vector<int> maximumBobPoints(int numArrows, vector<int> &aliceArrows) { int n = aliceArrows.size(); int state = 0, mx = -1; for (int mask = 1; mask < 1 << n; ++mask) { int cnt = 0, points = 0; for (int i = 0; i < n; ++i) { if ((mask >> i) & 1) { cnt += aliceArrows[i] + 1; points += i; } } if (cnt <= numArrows && mx < points) { state = mask; mx = points; } } vector<int> ans(n); for (int i = 0; i < n; ++i) { if ((state >> i) & 1) { ans[i] = aliceArrows[i] + 1; numArrows -= ans[i]; } } ans[0] += numArrows; return ans; }};class Solution: def maximumBobPoints(self, numArrows: int, aliceArrows: List[int]) -> List[int]: n = len(aliceArrows) state = 0 mx = - 1 for mask in range(1 << n): cnt = points = 0 for i, alice in enumerate(aliceArrows): if (mask >> i) & 1: cnt += alice + 1 points += i if cnt <= numArrows and mx < points: state = mask mx = points ans = [0] * n for i, alice in enumerate(aliceArrows): if (state >> i) & 1: ans[i] = alice + 1 numArrows -= ans[i] ans[0] = numArrows return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.