Section Recap

You learned the Aliens Trick for "exactly $K$" constraints:

$1.$ Add penalty $\lambda$ per item/segment to remove the $K$ dimension.

$2.$ Binary search on $\lambda$ to hit exactly $K$ items.

$3.$ Verify convexity: marginal benefit must decrease.

$4.$ Track counts during DP to guide binary search. You solved four problems: Building a Tall Barn (clearest convexity), Levels and Regions (standard partition), Gosha is Hunting (two constraints), and IOI 2016 Aliens (combined with CHT). This technique is rare but effective when it applies.