progress

~/problems / Search tricks / Meet in the middle

Trail mix with two exact targets

On a phone? Coding is easier on a laptop: email this problem to yourself . Meanwhile: quiz this topic or fight a boss.

medium ~25 min

You're packing trail mix from snack packets; packets[i] = (protein_i, sugar_i) grams. Take each packet at most once, and hit exactly protein grams of protein and exactly sugar grams of sugar.

Write count_mixes(packets: list[tuple[int, int]], protein: int, sugar: int) -> int: how many subsets (by position, so identical packets count separately) hit both targets. The empty subset counts when both are 0.

count_mixes([(3, 1), (2, 2), (1, 1), (4, 2)], 5, 3)   # 2   ((3,1)+(2,2) and (4,2)+(1,1))
count_mixes([(1, 1), (1, 1)], 1, 1)                   # 2   (either packet)
count_mixes([(5, 5)], 0, 0)                           # 1   (take nothing)
count_mixes([(2, 3)], 2, 4)                           # 0

Up to 34 packets; all gram values up to 10^9, so a DP over sums won't fit.

⭐ Bonus: trying all 2^n subsets still passes the smaller tests; the speed tests with 34 packets earn a star at about 2^(n/2) work (split the packets in half).

Show hint

a mix is some packets from the first half plus some from the second (at most 2^17 subsets each). Count one half's (protein, sugar) totals in a dict, then look up the partner each subset of the other half needs.

Topic: Meet in the middle. Split n ~ 40 into two halves of 2^20 and combine with sort + two pointers.

0:00
Ctrl ' run · Ctrl ↵ submit
esc