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).
nparcels must be shipped in the given order; parceliweighsw[i]kg. Each day the truck takes the next few parcels, and their total weight must be at most the capacityC. What is the smallestCthat ships everything withinkdays?
1 ≤ k ≤ n ≤ 2·10^5,1 ≤ w[i] ≤ 10^9(so the answer can reach 2·10^14).
| Sample input | Sample output |
|---|---|
7 34 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
-
Place
kshops at some of the positions1 2 4 8 9so the smallest gap between chosen shops is as large as possible, fork = 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. -
Largest
xwithx · x ≤ 10^18, withoutsqrt.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>. -
Trace the
lo = midbug 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. -
Why is
hi = sum of weightsalways 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
- 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)).
- Split an array into k contiguous parts minimising the largest sum? Exactly Courier Truck: binary search the largest sum with the greedy check.
- Why
lo + (hi − lo) / 2? It never overflows, unlikelo + hi. - How do you avoid infinite loops? With
hi = midon yes, uselo = mid + 1on no (andmidrounded down), so the range shrinks every step. - 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 = midloops forever (TLE on the sample);accumulate(..., 0)printed1000000000instead of3000000000.- Spot it: "minimise the maximum", easy check, huge range.
Next episode: ternary search: finding the bottom of a valley.