We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Points in an Archery Competition

Number: 2318

Difficulty: Medium

Paid? No

Companies: Kakao

Problem Description

Alice and Bob compete in an archery contest where the target is divided into scoring sections from 0 to 11. Alice has already shot her arrows with a known distribution across these sections. Bob now has numArrows arrows and wants to maximize his total score. To win a section and obtain its k points, Bob must shoot strictly more arrows in that section than Alice did (i.e. at least aliceArrows[k] + 1). If he does not exceed Alice’s count for a section, then Alice gets those points (unless neither shot any arrows at that section). The goal is to find one valid allocation of Bob’s arrows across the sections such that the sum of arrows equals numArrows and his total point score is maximized.

Key Insights

  • To win a section k, Bob must allocate (aliceArrows[k] + 1) arrows.
  • Each section has a “cost” (number of arrows needed) and a “value” (the score k), turning the selection into a knapsack-like problem.
  • With only 12 scoring sections, it is computationally feasible to iterate through all 2^12 possible subsets of sections.
  • After selecting the best subset of sections to win, any leftover arrows can be assigned arbitrarily (for example, to section 0) since section 0’s score is 0 and extra arrows do not affect the win condition.

Space and Time Complexity

Time Complexity: O(2^12) (approximately 4096 iterations), which is efficient because the number of sections is fixed at 12. Space Complexity: O(12) for the additional storage for the solution and recursion/iteration variables.

Solution

The problem is approached by considering each section independently as an item in a knapsack. For each section k, Bob can win it by spending (aliceArrows[k] + 1) arrows to earn k points. We enumerate all possible combinations (subsets) of sections that Bob could win. For every subset, we sum up the cost (arrows needed) and the total points. If the cost does not exceed numArrows, we update our best solution if the current subset yields a higher total score. Once the optimal combination is identified, we convert this subset into an allocation array (bobArrows) where for every section that Bob wins, we assign (aliceArrows[k] + 1) arrows. Finally, we distribute any remaining arrows (numArrows minus allocated arrows) — for example, by adding them to section 0 (which gives 0 points) to ensure the sum equals numArrows.

Code Solutions

# Python solution with line-by-line comments

def maximumBobPoints(numArrows, aliceArrows):
    bestScore = -1        # Best total score found so far
    bestMask = 0          # Bitmask representing the sections where Bob wins
    
    # There are 12 sections, so iterate over all possible subsets (0 to 2^12-1)
    for mask in range(1 << 12):
        totalCost = 0     # Total arrows needed for this subset
        totalScore = 0    # Total points earned for winning sections in this subset
        
        # Check each section (0 to 11)
        for section in range(12):
            # If the bit for this section is set, Bob wins this section
            if mask & (1 << section):
                totalCost += aliceArrows[section] + 1  # Arrows required to beat Alice
                totalScore += section                    # Points earned (section value)
                # Early break if cost already exceeds available arrows
                if totalCost > numArrows:
                    break
        else:
            # If totalCost is within limit, update best solution if current score is higher
            if totalCost <= numArrows and totalScore > bestScore:
                bestScore = totalScore
                bestMask = mask

    # Build the final allocation array for Bob based on bestMask
    bobArrows = [0] * 12
    usedArrows = 0
    
    # For each section, if chosen in bestMask, assign required arrows.
    for section in range(12):
        if bestMask & (1 << section):
            required = aliceArrows[section] + 1
            bobArrows[section] = required
            usedArrows += required

    # Assign any leftover arrows arbitrarily (here, to section 0)
    leftover = numArrows - usedArrows
    bobArrows[0] += leftover
    
    return bobArrows

# Example usage:
print(maximumBobPoints(9, [1,1,0,1,0,0,2,1,0,1,2,0]))
← Back to All Questions