The Smallest Stone Left Over
Stones have given weights. Repeatedly pick any two and smash them: if they weigh
the same both are destroyed, otherwise both are destroyed and a stone of the
DIFFERENCE appears. Print the smallest weight that can remain, or 0 if nothing
can.
2 7 4 1 8 1 -> 1
Problem #868 smashes the two HEAVIEST each time, which is a fixed rule and a different question. Here the pairing is free, and simulating choices is exponential.
The reframing is the whole problem. Every stone ends up contributing either +w
or -w to the final weight, depending on which side of the smashes it fell on.
So the stones split into two groups with totals A and B, and the answer is
|A - B|.
With S = A + B fixed, minimising |A - B| means pushing A as close to S/2 as
possible from below. So:
find the largest reachable subset sum A <= S/2
answer = S - 2A
which is problem 422's reachability table read differently: instead of asking
whether S/2 is reachable, ask for the largest reachable value at or below it.
The inner loop runs DOWNWARD, because each stone may be used once. That is the same rule as 422 and 439 and the opposite of 438.
Worth checking by hand: a single stone cannot be smashed at all, so it remains
whole, and the formula gives S - 0 = S.