# Maximum Points in an Archery Competition
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-points-in-an-archery-competition)
Canonical: https://scaleengineer.com/dsa/problems/maximum-points-in-an-archery-competition
**Patterns:** [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Data structures:** Array
**Companies:** [Kakao](https://scaleengineer.com/companies/kakao)
---
## Problem
Alice and Bob are opponents in an archery competition. The competition has set the following rules:

1. Alice first shoots `numArrows` arrows and then Bob shoots `numArrows` arrows.
2. The points are then calculated as follows:  
  1. The target has integer scoring sections ranging from `0` to `11` **inclusive**.
  2. For **each** section of the target with score `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.
  3. However, if `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:**

![](https://assets.glich.co/dsa/maximum-points-in-an-archery-competition/image0.jpg) 

**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:**

![](https://assets.glich.co/dsa/maximum-points-in-an-archery-competition/image1.jpg) 

**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 <= 105`
* `aliceArrows.length == bobArrows.length == 12`
* `0 <= aliceArrows[i], bobArrows[i] <= numArrows`
* `sum(aliceArrows[i]) == numArrows`

# Approaches
## Dynamic Programming (0/1 Knapsack)
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).
**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`.
**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 if `numArrows` is very large.
### Explanation
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:
1.  **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 is `dp[i+1][j]`.
2.  **Win section `i`**: Bob uses `cost = aliceArrows[i] + 1` arrows. This is only possible if `j >= cost`. The score would be `i + dp[i+1][j - cost]`.
The `dp[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 is `dp[0][numArrows]`.
After computing the entire DP table, we reconstruct the `bobArrows` array by backtracking through the table, starting from `dp[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 in `bobArrows[0]`.
```java
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;
    }
}
```
### 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 sections `i` to `11` with `j` arrows.
- The table size will be `(12 + 1) x (numArrows + 1)`.
- Fill the table iteratively from `i = 11` down to `0` and `j = 0` to `numArrows`.
- The recurrence relation for `dp[i][j]` is `max(score_if_concede, score_if_win)`:
  - `score_if_concede = dp[i+1][j]`
  - `score_if_win = i + dp[i+1][j - (aliceArrows[i] + 1)]` (if `j` is sufficient).
- The maximum possible score is `dp[0][numArrows]`.
- Reconstruct the `bobArrows` array by tracing back the decisions made in the DP table that led to the optimal score.
- Start with `arrowsLeft = numArrows` and iterate from `i = 0` to `11`.
- 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 update `arrowsLeft`.
- Allocate any remaining arrows to `bobArrows[0]`.

## Iterative Brute Force with Bitmasking
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.
**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.
**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.
### Explanation
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]`.
```java
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;
    }
}
```
### Algorithm
- Initialize `maxScore = -1` and `bestBobArrows` to an empty or default array.
- Loop a variable `mask` from `0` to `(1 << 12) - 1`.
- Inside the loop, for each `mask`:
    - Initialize `currentScore = 0`, `arrowsUsed = 0`, and a temporary `currentBobArrows` array.
    - Loop `j` from 0 to 11.
    - If the `j`-th bit of `mask` is 1, it signifies winning section `j`. Update `currentScore`, `arrowsUsed`, and `currentBobArrows[j]`.
    - After the inner loop, check if `arrowsUsed <= numArrows`.
    - If it is a valid combination, and if `currentScore > maxScore`, update `maxScore` and `bestBobArrows`. Remember to add the remaining arrows (`numArrows - arrowsUsed`) to `bestBobArrows[0]`.
- After iterating through all masks, return `bestBobArrows`.

## Recursive Backtracking
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.
**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.
**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).
### Explanation
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:
1.  **Win section `index`**: If `arrowsLeft` is sufficient to use `aliceArrows[index] + 1` arrows, we make this choice. We update `currentBobArrows`, decrement `arrowsLeft`, add `index` to `currentScore`, and recurse for `index - 1`.
2.  **Concede section `index`**: We use 0 arrows for this section and recurse for `index - 1` with unchanged `arrowsLeft` and `currentScore`.
The base case for the recursion is when `index < 0`, meaning decisions have been made for all sections. At this point, we check if the `currentScore` is the best we've seen. If so, we update our global `maxScore` and `bestBobArrows` solution. Any `arrowsLeft` are added to `bestBobArrows[0]`.
To avoid carrying state changes between different recursive branches, we must "backtrack" after a recursive call returns, by undoing the changes made to `currentBobArrows`.
```java
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);
    }
}
```
### Algorithm
- Define a recursive helper function `backtrack(index, arrowsLeft, currentBobArrows, currentScore)`.
- Use global variables `maxScore` and `bestBobArrows` to keep track of the best solution found.
- The initial call is `backtrack(11, numArrows, new int[12], 0)`.
- In the `backtrack` function:
    - **Base Case**: If `index < 0`, all decisions are made. Compare `currentScore` with `maxScore` and update the global best solution if necessary. Add `arrowsLeft` to the `[0]` index of the solution.
    - **Recursive Step**:
        - Explore the path of winning section `index`: If `arrowsLeft` is sufficient, update `currentBobArrows`, `arrowsLeft`, `currentScore`, and make a recursive call for `index - 1`. After the call returns, revert the changes to `currentBobArrows` (this is the "backtracking" step).
        - Explore the path of conceding section `index`: Make a recursive call for `index - 1` without changing the state.

# Solutions
### Java

```java
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;
  }
}

```

### JavaScript

```javascript
/** * @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;
  };

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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 ans

```