Binary Search on the Answer Practice Test: Timed C++ Quiz
A timed 45-minute practice test on binary search on the answer: monotone checks, bounds, rounding mid, overflow in the check and factory machines.
- Course: Competitive Programming study plan
- Module: Binary search on the answer
- Kind: Checkpoint — cleared at 70%
- Reading time: 45 min
- Runtime: Clang 18 · C++20
Checkpoint — Binary search on the answer is the checkpoint that closes the Binary search on the answer module: a graded quiz and whole-program exercises, passed at 70%.
Instructions
A timed checkpoint on binary search on the answer: recognising the shape, proving the bounds, the two loop templates and the overflow traps.
How it works. Ten questions and one program, in 45 minutes from when you start the timer. Clear 70% of the questions and get the program accepted on every hidden case — including answers near 10¹⁸ — to complete the module.
Before you start, make sure you can answer these from memory:
- What makes a yes/no check monotone, and why that is what binary search needs.
- The first-yes template (
hi = mid,lo = mid + 1) and the last-yes template (lo = mid,hi = mid - 1,midrounded up). - How to prove
loandhifrom the constraints. - Why a sum inside the check can overflow
long long, and how to stop it. - How many checks a range of 10⁹ or 10¹⁸ takes.
Common questions
How do you choose hi in a binary search on the answer?
Pick a value you can prove is feasible from the statement's limits. For the factory problem, the fastest machine alone makes t products in min(k) * t seconds, so that time certainly works. If hi might be infeasible, the search returns it anyway and the answer is wrong.
Why can the check in a binary search on the answer overflow?
The check often sums values derived from the guess, like T / k_i over every machine. With T near 10^18 two such terms already pass the long long range. Stop summing as soon as the target is reached, or cap each term.
Exercise
Factory machines
A factory has n machines. Machine i makes one product every k_i seconds, and all machines work at the same time. What is the shortest time in which they can make t products together?
Input: n t (1 ≤ n ≤ 2·10^5, 1 ≤ t ≤ 10^9), then n integers k_i (1 ≤ k_i ≤ 10^9). Output: one integer, the minimum time in seconds.
3 7
3 2 5prints
8In 8 seconds the machines make 2 + 4 + 1 = 7 products; in 7 seconds only 2 + 3 + 1 = 6. The answer can reach 10¹⁸ — and adding up T / k_i over every machine can overflow even long long.
In this module: Binary search on the answer
← Binary search on the answer — guess, check, halve · Greedy algorithms — choose, then prove by exchange →