- Difficulty: Medium
- Tags: LeetCode, Medium, Bit Manipulation, Array, Backtracking, Enumeration, leetcode-2212, O(n * 2^n), O(n), Bitmasks, Brute Force
Problem
Alice and Bob are opponents in an archery competition. The competition has set the following rules:
- Alice first shoots
numArrows
arrows and then Bob shootsnumArrows
arrows. - The points are then calculated as follows:
- The target has integer scoring sections ranging from
0
to11
inclusive. - For each section of the target with score
k
(in between0
to11
), say Alice and Bob have shotak
andbk
arrows on that section respectively. Ifak >= bk
, then Alice takesk
points. Ifak < bk
, then Bob takesk
points. - However, if
ak == bk == 0
, then nobody takesk
points.
- The target has integer scoring sections ranging from
-
For example, if Alice and Bob both shot
2
arrows on the section with score11
, then Alice takes11
points. On the other hand, if Alice shot0
arrows on the section with score11
and Bob shot2
arrows on that same section, then Bob takes11
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 <= 105
aliceArrows.length == bobArrows.length == 12
0 <= aliceArrows[i], bobArrows[i] <= numArrows
sum(aliceArrows[i]) == numArrows