At what height do you cut the cakes?

A dessert shop owner lines up cakes of all different heights on the display shelf. To set up a free tasting corner, the owner sets the cutter's blade to some height H and slices all the cakes at once, horizontally.

Every cake taller than H has its top sliced off, and all those tops are gathered as tasting pieces. Here's the catch — the lower the blade, the more is cut and the more you collect, but the display cakes get ruined to that extent.

So the goal is to meet exactly the required tasting amount while keeping the blade as high as possible to minimize damage.

Example: cake heights 15, 22, 9, 18, 30, 25, needing a tasting amount of 18. Answer: 19. (At H=19, (22-19)+(30-19)+(25-19) = 20 ≥ 18; at H=20 it is 17, not enough.)

How do you approach this? (The core idea)

It feels hopeless at first. Deciding *which* cakes to cut and by *how much* explodes the number of cases.

Flip it — don't choose where to cut. Assume the answer (blade height H) first.

•"When the blade is at height H, is the collected amount at least what we need?" → this is a quick scan over all cakes: Σ max(0, height - H).
•Low H cuts a lot (feasible); high H cuts little (infeasible). So feasibility is monotonic in H.
•Monotonic? Then binary search finds the largest H that still meets the amount.

That's parametric search — *binary-searching the answer itself.* You're not searching values in a sorted array; you're narrowing the range of candidate answers (0 ~ the tallest cake).

Why is it confusing?

Most people learn "binary search = find a value in a sorted array." So *"binary-search the answer"* rarely comes to mind at first.

But once you see it, it clicks:

1. Pick a candidate height H (the middle of the range = mid)

2. Draw the blade at that H and add up everything sliced above it

3. If it's enough, raise H (try a higher blade); if not, lower it

4. The range narrows and converges to the answer

Following this as a step-by-step animation makes "*ah, that's* why it's binary search" land instantly.

See it with your own eyes

We built the entire process as a step-by-step visualization: cakes standing as bars, the red blade line (H) moving up and down, and the sliced tops highlighted at a glance — with every variable (lo·mid·hi, collected amount) visible.

👉 Cake Cutting — watch the step-by-step visualization

Parametric search shows up in coding tests in countless disguises ("cutting trees", "router setup", "budget split"). Learn the principle visually once, and you can solve any variant.