Maximum Points in an Archery Competition — LeetCode 2212 Python Solution

The 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 shoots numArrows arrows.

Example

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.

Python solution

class Solution:
    def maximumBobPoints(self, numArrows: int, aliceArrows: List[int]) -> List[int]:
        st = mx = 0
        m = len(aliceArrows)
        for mask in range(1, 1 << m):
            cnt = s = 0
            for i, x in enumerate(aliceArrows):
                if mask >> i & 1:
                    s += i
                    cnt += x + 1
            if cnt <= numArrows and s > mx:
                mx = s
                st = mask
        ans = [0] * m
        for i, x in enumerate(aliceArrows):
            if st >> i & 1:
                ans[i] = x + 1
                numArrows -= ans[i]
        ans[0] += numArrows
        return ans

Complexity

Pattern: Backtracking

Build candidates one choice at a time and abandon a branch the moment it cannot work. LeetCode 2212. Maximum Points in an Archery Competition is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Backtracking.

The backtracking guide has the Python template for the pattern and the 105 LeetCode problems that use it.

Related problems