Divide Chocolate

Divide Chocolate looks like a partitioning puzzle, but it is really a binary search on the answer. The trick is realising you can guess the result and cheaply check whether the guess is achievable.

The slow way first

You could try every way to place the k cuts and take the best minimum. The number of cut placements blows up combinatorially, so that is hopeless for a real bar.

The question to ask: instead of building the answer, can I guess it and verify? Suppose I claim "every piece can have sweetness at least x." Checking that claim is easy — walk the bar greedily and count how many pieces of sum >= x I can carve out. If I can make at least k + 1 of them, the claim holds.

The idea: binary-search the minimum piece

The achievable minimum is monotonic: if x is achievable, every smaller value is too; if x is not, nothing larger is. That monotonic yes/no line is exactly what binary search hunts for.

So we search the value range [min(sweetness), sum(sweetness)]. For each candidate mid, we greedily count pieces: accumulate a running sum and cut a piece the moment it reaches mid. If we get at least k + 1 pieces, mid is feasible — try larger. Otherwise shrink.

The greedy count is correct because making each piece barely reach mid leaves the most chunks behind for later pieces — it maximises how many pieces we can form.

Walk through it

Step through the animation. The pointer i sweeps the bar accumulating a running sum. Each time it reaches the candidate mid, a piece is cut and the sum resets. We compare the piece count against k + 1, then nudge lo up (feasible) or hi down (too big). The window narrows until it lands on 6.

Pseudocode

lo = smallest single chunk
hi = sum of all chunks
while lo <= hi:
    mid = (lo + hi) / 2
    pieces = 0, run = 0
    for each chunk s:
        run += s
        if run >= mid:        # this piece is big enough -> cut it
            pieces += 1
            run = 0
    if pieces >= k + 1:       # feasible: push for a larger minimum
        lo = mid + 1
    else:                     # too greedy: lower the target
        hi = mid - 1
return hi                     # largest value that was feasible

The Python solution

def maximize_sweetness(sweetness, k):
    lo = min(sweetness)
    hi = sum(sweetness)
    while lo <= hi:
        mid = (lo + hi) // 2
        # greedily count pieces with sum >= mid
        pieces = 0
        run = 0
        for s in sweetness:
            run += s
            if run >= mid:
                pieces += 1
                run = 0
        if pieces >= k + 1:
            # feasible: try for a larger minimum
            lo = mid + 1
        else:
            # too big: lower the minimum
            hi = mid - 1
    return hi

• lo and hi bound the answer value, not array indices — the smallest possible minimum and the largest.
• mid is the candidate minimum sweetness we are testing this round.
• The inner loop is the feasibility check: accumulate run, and whenever it reaches mid, cut a piece and reset.
• pieces >= k + 1 means the candidate is achievable, so we greedily try for a bigger minimum with lo = mid + 1.
• When the loop ends, hi holds the last feasible value — that is the maximised minimum.

Complexity

We replace an exponential search over cut placements with O(log S) cheap O(n) checks. The pattern — binary search the answer, verify with a greedy linear scan — is the whole move.

When this pattern shows up

Practice