SyntaxPilot
Courses/Competitive Programming/Lesson 11
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Competitive Programming · Lesson 11 of 90

Binary search on the answer

queued

These are the notes for Competitive Programming episode 11. An original problem, Courier Truck, asks for the smallest truck capacity that ships parcels in order within k days. Checking one capacity is an easy greedy, but trying capacities one by one gets Time Limit Exceeded when the answer is 10^14. A guess-the-price game fixes it: the yes/no answers are monotonic (once a capacity works, every bigger one works), so guess the middle and throw half away. That is binary search on the answer: 48 checks instead of 10^14. You also see two bugs with real outputs: an infinite loop and a silent overflow. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.

The problem: Courier Truck

Problem K · Courier Truck (written for this course). n parcels must be shipped in the given order; parcel i weighs w[i] kg. Each day the truck takes the next few parcels, and their total weight must be at most the capacity C. What is the smallest C that ships everything within k days?

1 ≤ k ≤ n ≤ 2·10^5, 1 ≤ w[i] ≤ 10^9 (so the answer can reach 2·10^14).

Sample input Sample output
7 3
4 2 7 3 5 1 6
12

With C = 12: [4 2] [7 3] [5 1 6], 3 days. With C = 11: [4 2] [7 3] [5 1] [6], 4 days.

Checking one guess is easy

Given C, load parcels until the next one doesn't fit, then start a new day. Loading as much as possible each day never hurts, so this greedy check is correct, and it is one O(n) pass:

bool ok(ll C) {
    int days = 1;
    ll load = 0;
    for (ll x : w) {
        if (load + x > C) {
            days++;
            load = 0;
        }
        load += x;
    }
    return days <= k;
}

(It assumes C ≥ the heaviest parcel; the search below makes sure of that.)

Brute force: try every C

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, k;
vector<ll> w;

bool ok(ll C) {
    int days = 1;
    ll load = 0;
    for (ll x : w) {
        if (load + x > C) {
            days++;
            load = 0;
        }
        load += x;
    }
    return days <= k;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> k;
    w.resize(n);
    for (auto &x : w) cin >> x;
    ll C = *max_element(w.begin(), w.end());
    while (!ok(C)) C++;
    cout << C << '\n';
    return 0;
}

Correct on the sample (12). A max test made in code (n = 2·10^5 parcels of 10^9 kg, k = 2, answer 10^14) tries up to 10^14 capacities, each an O(n) check, and got Time Limit Exceeded in the SyntaxPilot compiler.

The idea: the guess-the-price game

Guess-the-price game In code
The host only says yes or no: "is it at most ₹500?" ok(C) is a yes/no check
If ₹600 is enough, ₹700 is enough too: no, no, no, then yes forever monotonic predicate: ✗ ✗ ✗ ✓ ✓ ✓
Always guess the middle: half the prices are gone mid = lo + (hi - lo) / 2
₹1 to ₹1000 in 10 guesses (2^10 = 1024) 10^14 in about 47 checks (log2)

On the sample, ok flips once, at 12:

C 7 8 9 10 11 12 13 14 15 16 17
ok(C) ✗ ✗ ✗ ✗ ✗ ✓ ✓ ✓ ✓ ✓ ✓

The search, starting from lo = 7 (heaviest parcel) and hi = 28 (total weight, always enough):

lo hi mid ok(mid) next
7 28 17 yes hi = 17
7 17 12 yes hi = 12
7 12 9 no lo = 10
10 12 11 no lo = 12
12 12 answer 12 (4 checks)

Binary search on the answer

lo = smallest value that could be the answer
hi = a value that surely works
while (lo < hi):
    mid = lo + (hi - lo) / 2
    if ok(mid): hi = mid        // mid might be the answer: keep it
    else:       lo = mid + 1    // mid is too small: skip it
answer = lo

Invariant (a promise that stays true every step): the answer is inside [lo, hi]. Each step halves the range, so it takes about log2(hi − lo) checks. Writing lo + (hi − lo) / 2 instead of (lo + hi) / 2 avoids overflow when lo and hi are huge.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, k;
vector<ll> w;

bool ok(ll C) {
    int days = 1;
    ll load = 0;
    for (ll x : w) {
        if (load + x > C) {
            days++;
            load = 0;
        }
        load += x;
    }
    return days <= k;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> k;
    w.resize(n);
    for (auto &x : w) cin >> x;
    ll lo = *max_element(w.begin(), w.end());
    ll hi = accumulate(w.begin(), w.end(), 0LL);
    while (lo < hi) {
        ll mid = lo + (hi - lo) / 2;
        if (ok(mid)) hi = mid;
        else lo = mid + 1;
    }
    cout << lo << '\n';
    return 0;
}

Sample output: 12. On the max test, with a counter:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, k;
vector<ll> w;

bool ok(ll C) {
    int days = 1;
    ll load = 0;
    for (ll x : w) {
        if (load + x > C) {
            days++;
            load = 0;
        }
        load += x;
    }
    return days <= k;
}

int main() {
    n = 200000, k = 2;   // a max test, made in code
    w.assign(n, 1000000000);
    auto start = chrono::steady_clock::now();
    ll lo = *max_element(w.begin(), w.end());
    ll hi = accumulate(w.begin(), w.end(), 0LL);
    int checks = 0;
    while (lo < hi) {
        ll mid = lo + (hi - lo) / 2;
        checks++;
        if (ok(mid)) hi = mid;
        else lo = mid + 1;
    }
    auto ms = chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() - start).count();
    cout << lo << " after " << checks << " checks, " << ms << " ms\n";
    return 0;
}

Output (time varies by machine, a few ms):

100000000000000 after 48 checks, 4 ms

Bug 1: lo = mid loops forever (real verdict)

Change else lo = mid + 1; to else lo = mid; and run the sample: Time Limit Exceeded, on 7 parcels. When lo = 11 and hi = 12, mid = 11 (rounded down); ok(11) is no, so lo = mid = 11 again. Nothing changes, forever. When the check says no, mid is definitely not the answer, so skip it: every step must make the range smaller.

Bug 2: accumulate(..., 0) overflows (real output)

accumulate's last argument decides the type of the sum. With a plain 0 the sum is an int:

ll hi = accumulate(w.begin(), w.end(), 0);      // int sum

Input 3 1 / 1000000000 1000000000 1000000000, output:

1000000000

The answer is 3·10^9. The int sum overflowed to a negative number, so hi < lo, the loop never ran, and lo (10^9) was printed, with no error message. With 0LL the output is 3000000000.

How to spot it in a contest

  • The statement says minimise the maximum or maximise the minimum.
  • Finding the answer directly is hard, but checking a guess is easy (often a greedy).
  • The check is monotonic: once yes, always yes (or the reverse).
  • The answer range is huge (10^9, 10^14, 10^18).

Solutions in C++, Java and Python

C++: the binary-search program above.

Java

import java.io.*;
import java.util.*;

public class Main {
    static long[] w;
    static int k;

    static boolean ok(long C) {
        int days = 1;
        long load = 0;
        for (long x : w) {
            if (load + x > C) { days++; load = 0; }
            load += x;
        }
        return days <= k;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer t = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(t.nextToken());
        k = Integer.parseInt(t.nextToken());
        w = new long[n];
        t = new StringTokenizer(br.readLine());
        long lo = 0, hi = 0;
        for (int i = 0; i < n; i++) {
            w[i] = Long.parseLong(t.nextToken());
            lo = Math.max(lo, w[i]);
            hi += w[i];
        }
        while (lo < hi) {
            long mid = lo + (hi - lo) / 2;
            if (ok(mid)) hi = mid;
            else lo = mid + 1;
        }
        System.out.println(lo);
    }
}

Python

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n, k = int(data[0]), int(data[1])
    w = list(map(int, data[2:2 + n]))

    def ok(C):
        days, load = 1, 0
        for x in w:
            if load + x > C:
                days += 1
                load = 0
            load += x
        return days <= k

    lo, hi = max(w), sum(w)
    while lo < hi:
        mid = (lo + hi) // 2
        if ok(mid):
            hi = mid
        else:
            lo = mid + 1
    print(lo)

main()

All three print 12 on the sample.

Brute force vs optimal

Try every C Binary search on C
Checks up to 2·10^14 ⌈log2(range)⌉ ≈ 48
Time O(range · n), TLE O(n · log(range)) ≈ 10^7
Needs nothing a monotonic check

Common mistakes (and the real messages)

Mistake What you see Why Fix
else lo = mid; Time Limit Exceeded (on the sample) lo 11, hi 12 → mid 11 forever else lo = mid + 1;
accumulate(..., 0) 1000000000 instead of 3000000000 the sum is computed in int accumulate(..., 0LL)
lo = 1 with this ok wrong answer ok never checks a single parcel fits lo = max weight, or if (x > C) return false;
int lo, hi, mid overflow / wrong answer lo + hi passes 2.1·10^9 long long, lo + (hi − lo) / 2
Non-monotonic check wrong answer binary search jumps past the answer prove "once yes, always yes" first

Mini project: toy factory

n machines; machine i makes one toy every t[i] seconds, all working at once. How long until m toys are made? The check ok(T) = Σ T / t[i] ≥ m is monotonic in T:

auto ok = [&](ll T) {
    ll made = 0;
    for (ll x : t) {
        made += T / x;
        if (made >= m) return true;   // stop early: avoids overflow
    }
    return false;
};
ll lo = 1, hi = *min_element(t.begin(), t.end()) * m;   // the fastest machine alone is enough
while (lo < hi) {
    ll mid = lo + (hi - lo) / 2;
    if (ok(mid)) hi = mid;
    else lo = mid + 1;
}

With t = 3 2 5 and m = 10: at T = 10 the machines make 3 + 5 + 2 = 10 toys; at T = 9 only 3 + 4 + 1 = 8. Answer 10.

Practice

  1. Place k shops at some of the positions 1 2 4 8 9 so the smallest gap between chosen shops is as large as possible, for k = 3.

    Answer Binary search the gap <code>g</code>; check greedily (take the first position, then the next one at least <code>g</code> further). Answer <code>3</code> (1, 4, 8 or 1, 4, 9). Maximise the minimum: the check is "can I place k shops with gap ≥ g", yes for small g, no for big g.

  2. Largest x with x · x ≤ 10^18, without sqrt.

    Answer <code>10^9</code>. Binary search on x in [0, 2·10^9]; compare <code>x <= N / x</code> (or use <code>__int128</code>) to avoid overflow in <code>x * x</code>.

  3. Trace the lo = mid bug on the sample on paper.

    Answer (7, 28) → mid 17 yes → (7, 17) → mid 12 yes → (7, 12) → mid 9 no → (9, 12) → mid 10 no → (10, 12) → mid 11 no → (11, 12) → mid 11 no → (11, 12) … forever.

  4. Why is hi = sum of weights always enough?

    Answer With C = total weight, everything fits in one day, and k ≥ 1.

Quick quiz

k = 2 days, parcels 5 5 5 5. Smallest capacity?

A) 5 · B) 10 · C) 15 · D) 20

Answer

B. C = 10 ships [5 5] [5 5]. With C = 9 only one parcel fits a day: 4 days.

Interview questions

  1. What is binary search on the answer? Searching over possible answers with a yes/no check that is monotonic, halving the range each step: O(check · log(range)).
  2. Split an array into k contiguous parts minimising the largest sum? Exactly Courier Truck: binary search the largest sum with the greedy check.
  3. Why lo + (hi − lo) / 2? It never overflows, unlike lo + hi.
  4. How do you avoid infinite loops? With hi = mid on yes, use lo = mid + 1 on no (and mid rounded down), so the range shrinks every step.
  5. Koko-eating-bananas style problems? Same pattern: binary search the speed, check total hours ≤ h.

Glossary

Term Meaning Example
Binary search Halving a range using a yes/no question 7..28 → 12 in 4 checks
Binary search on the answer Binary search over candidate answers instead of array positions the capacity C
Predicate / check A function that answers yes or no ok(C)
Monotonic predicate Answers flip only once (no, no, …, yes, yes) ✗✗✗✗✗✓✓✓
Greedy Take the locally best choice each step load until the next parcel doesn't fit
Invariant A fact kept true at every step answer ∈ [lo, hi]
lo, hi, mid The current range and its middle 7, 28, 17
log2 How many halvings reach 1 log2(10^14) ≈ 47
accumulate Sums a range; the start value sets the type accumulate(b, e, 0LL)
Minimise the maximum Make the worst part as small as possible the heaviest day

Summary

  • Checking a capacity is an O(n) greedy; trying every capacity is TLE when the answer is 10^14.
  • The check is monotonic, so binary search: ok(mid) ? hi = mid : lo = mid + 1, 48 checks.
  • lo = mid loops forever (TLE on the sample); accumulate(..., 0) printed 1000000000 instead of 3000000000.
  • Spot it: "minimise the maximum", easy check, huge range.

Next episode: ternary search: finding the bottom of a valley.