Maximum Points in an Archery Competition

Maximum Points in an Archery Competition

1. What is this problem about?

The Maximum Points in an Archery Competition interview question is a game-theory inspired optimization problem. Bob and Alice are in an archery competition with 12 sections (scored 0 to 11). For each section i, if Alice shoots a_i arrows, Bob must shoot at least a_i + 1 arrows to win that section and get i points. If Bob cannot win the section, he should ideally shoot 0 arrows there to save them for other sections. Bob has a limited number of arrows. The goal is to determine how Bob should distribute his arrows to maximize his total score.

2. Why is this asked in interviews?

This Maximum Points in an Archery Competition coding problem is often used by companies like Kakao to test a candidate's ability to explore a small search space efficiently. Since there are only 12 sections, the total number of ways to win or lose sections is $2^{12} = 4096$, which is quite small. This makes it a perfect problem for testing Bit Manipulation or Backtracking. It evaluates whether you can recognize when a "brute force" approach (exploring all winning combinations) is actually the most efficient solution due to small constraints.

3. Algorithmic pattern used

The Array, Enumeration, Backtracking, Bit Manipulation interview pattern is perfectly suited for this. You can represent the set of sections Bob wins as a bitmask from 0 to $2^{12}-1$. For each bitmask:

1. Calculate the total arrows Bob would need (sum of aliceArrows[i] + 1 for each bit i set in the mask).
2. If the total is less than or equal to Bob's total arrows, calculate the score (sum of i for each bit i set).
3. Keep track of the mask that gives the highest score.
4. Any remaining arrows Bob has can be dumped into the 0-th section (as it doesn't change the score) to satisfy the total arrow count.

4. Example explanation

Bob has 10 arrows. Alice's arrows: [1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0] for sections 0 to 11. If Bob wants to win section 11, he needs 0+1 = 1 arrow. Score = 11. Arrows left = 9. If Bob wants to win section 10, he needs 0+1 = 1 arrow. Score = 11 + 10 = 21. Arrows left = 8. ... and so on. Bob should prioritize higher-indexed sections because they give more points for fewer arrows (since Alice shot 0 arrows in sections 6-11). Winning 11, 10, 9, 8, 7, 6 uses 6 arrows. Score = 11+10+9+8+7+6 = 51. Remaining 4 arrows can be put in section 0.

5. Common mistakes candidates make

A frequent mistake in the Maximum Points in an Archery Competition coding problem is trying to use a greedy approach (e.g., always picking the section with the best point-to-arrow ratio). Greedy doesn't work here because it's a variation of the Knapsack problem. Another mistake is forgetting to handle the "remaining arrows." The problem usually requires Bob to use all his arrows, so any leftover arrows must be assigned to some section (usually the 0-th section is the safest). Also, ensure you are using the correct condition: Bob needs aliceArrows[i] + 1 to win, not just aliceArrows[i].

6. Interview preparation tip

When you see a problem with a very small input size (like 12 or 20), immediately think about bitmasks or exhaustive backtracking. These are often the intended solutions when the state space is small enough to fit in a standard integer. Practice converting bitmasks to set elements and vice versa, as this is a fundamental skill for competitive programming and technical interviews.