LC-2212 Medium LeetCode

2212. Maximum Points in an Archery Competition

Array Backtracking Bit Manipulation Enumeration

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 50% Topics: Array, Backtracking, Bit Manipulation, Enumeration

Reading material

Arrays & Hashing 12 min Backtracking 14 min Bit Manipulation 10 min

Reference solution (spoiler · python)

# Time:  O(n * 2^n)
# Space: O(n)

# bitmasks
class Solution(object):
    def maximumBobPoints(self, numArrows, aliceArrows):
        """
        :type numArrows: int
        :type aliceArrows: List[int]
        :rtype: List[int]
        """
        def check(mask, numArrows):
            score = 0
            cnt = [0]*len(aliceArrows)
            i, base = 0, 1
            for k, a in enumerate(aliceArrows):
                if mask&1:
                    need = a+1
                    if need > numArrows:
                        return 0, [0]*len(aliceArrows)
                    numArrows -= need
                    cnt[k] = need
                    score += k
                mask >>= 1
            cnt[-1] += numArrows
            return score, cnt
        
        result = [0]*len(aliceArrows)
        best = 0
        for mask in xrange(1, 2**len(aliceArrows)):
            score, cnt = check(mask, numArrows)
            if score > best:
                best = score
                result = cnt
        return result

Solution from kamyu104/LeetCode-Solutions · MIT