The Tallest Pair of Equal Stacks
Blocks of given heights are to be built into TWO stacks of exactly EQUAL height. Each
block may be used in one stack, the other, or left out entirely. Print the greatest
height the two stacks can reach, or 0 if no non-empty equal pair is possible.
1 2 3 6 -> 6 stacks {6} and {1,2,3}
1 2 -> 0 no equal pair exists
## Why the obvious state is too big
The natural state is the pair of stack heights, which needs sum^2 entries. With
heights summing to 5000 that is 2.5 * 10^7 per item and too slow.
## The state is the difference
Two stacks are interchangeable, so what matters is not which is which. And once the DIFFERENCE between them is known, together with the height of the SHORTER one, both heights are known.
dp[d] = the greatest height of the SHORTER stack, over all ways to reach difference d
The answer is dp[0], where the difference is zero and the shorter stack is therefore
both of them.
The difference only ever ranges over 0 .. sum, so the table is one-dimensional. That
is the trade: one dimension is bought by storing a value instead of a flag.
## The transitions
For a block of height v at difference d with shorter stack lo:
leave it out d stays, lo stays
add to TALLER d becomes d+v, lo stays the shorter one did not change
add to SHORTER d becomes |d-v|, lo becomes lo + min(v, d)
The third line is the one to get right. Adding v to the shorter stack raises it by
v, but if v exceeds the gap d the stacks SWAP roles, and the new shorter stack is
the old taller one, whose height is lo + d. Both cases are lo + min(v, d).
Writing lo + v instead is correct only while v <= d and silently overstates the
shorter stack whenever a block overshoots the gap.
## Reading the answer
dp[0] starts at 0, which represents two empty stacks. That is why "no equal pair
possible" and "the best equal pair has height 0" give the same output, and the statement
says 0 for both rather than pretending to distinguish them.
1 2 answers 0 and 5 answers 0: in both cases the only equal pair is the empty one.
## Boundaries
4 6 10 answers 10, from {10} against {4,6}, using every block.
1 1 1 1 answers 2, from two blocks against two. Not 1: the greedy of pairing equal
blocks one at a time stops early, and taking all four is better.
3 4 5 6 answers 9, from {4,5} against {3,6}, which is the case where no block is
left out and no obvious pairing exists.
Heights sum to at most 5000, so the difference index is small, but the stored heights still want a 64-bit accumulator in languages where the sum could grow.