USACO 2026 Chip Exchange: Binary Search on the Answer

Chip Exchange is a strong example of a contest pattern students often miss at first: binary search on the answer. The problem asks for the smallest extra amount that makes a target guaranteed. Trying possible amounts one by one is natural, but it fails when the answer can be large.

The pattern signal

Use binary search on the answer when all three of these are true:

• The output is the minimum or maximum number that works.
• Checking a proposed value is easier than directly finding the value.
• The check is monotonic: once a value works, every larger value works too.

Write the checker first

The central helper should answer one question:

Can this candidate amount guarantee the target?

For this style of problem, the main method should not understand every arithmetic detail. It should only know whether mid works.

while (lo < hi)
{
    long mid = lo + (hi - lo) / 2;
    if (canGuarantee(mid))
    {
        hi = mid;
    }
    else
    {
        lo = mid + 1;
    }
}

Why the search moves this way

If mid works, the smallest working answer might still be smaller, so the high side moves down. If mid fails, every smaller candidate also fails, so the low side moves above mid.

Common mistakes

• Binary searching before proving the check is monotonic.
• Using int when the candidate range needs long.
• Moving lo and hi in the wrong direction.
• Setting the upper bound too small and excluding the true answer.

Practice prompt

Create a different problem where you need the minimum number of extra practice problems for a student to reach a target score. Write only the checker first, then wrap it in binary search.