Binary search over the possible answers
The first-YES loop has so far searched the positions of an array, but the loop itself only needs a range of whole numbers and a monotone yes-or-no question about them. In the next problem the answer is not a position in any array, and the range will be the possible answers themselves.
A factory has machines, and machine takes seconds to make one product. The machines work at the same time, starting at time 0. What is the shortest time in which they can make products in total?
The first input line holds and , and the second line holds . Print the shortest time.
Constraints
Sample · Input
3 7 3 2 5
Output
8
In the sample the machines take 3, 2 and 5 seconds per product, and 7 products are wanted. A machine that takes seconds finishes a product at times , , and so on, so by time it has finished products, which is rounded down. A product that is still being made does not count. The table adds this up for the times 5 to 10.
| Time | 3-second machine | 2-second machine | 5-second machine | Total | At least 7? |
|---|---|---|---|---|---|
| 5 | 1 | 2 | 1 | 4 | NO |
| 6 | 2 | 3 | 1 | 6 | NO |
| 7 | 2 | 3 | 1 | 6 | NO |
| 8 | 2 | 4 | 1 | 7 | YES |
| 9 | 3 | 4 | 1 | 8 | YES |
| 10 | 3 | 5 | 2 | 10 | YES |
The total first reaches 7 at time 8, so the answer is 8.
The direct way to find that time is to try in order and stop at the first total that reaches the products wanted, 7 in the sample. Each try adds up one division per machine, in all, and the number of tries is the answer itself. With a single machine that needs seconds per product and products wanted, the answer is , so this loop can take tries.
Now read the last column from top to bottom: NO, NO, NO, YES, YES, YES. The question "have the machines finished at least products by time ?" is monotone. A finished product stays finished, so with more time the total can only stay the same or go up, and once it has reached it never falls below again. The problem asks for the first time at which this question gets a YES, which is what the first-YES loop finds.
Using binary search this way is called searching on the answer. The candidates are the possible answers, and a function called the check says whether one candidate works.
Choose the range of times to search
The loop needs a first and a last candidate. Time 1 is the smallest time that could work, so the range starts there. The last candidate has to be a time that certainly works, so that the range contains a YES. One such time is : by then the fastest machine has finished products on its own, and the other machines only add to the total. For the sample that is .
The loop probes the times 7, 11, 9 and 8. The totals there are 6, 10, 8 and 7, so it gets one NO and then three YES answers, and the last YES it saves is time 8. It computed four totals, where the direct loop from time 1 computes eight.
Halve the candidate range with binary search
In this stepper you make the decision at each probe. The purple cell is mid, the line under the cells gives its answer, and you choose which side of mid to keep searching. A wrong choice is explained and not applied.
The Sorted list tab looks for the first value at least 12 in [3, 8, 11, 14, 20, 27]. The Machines tab searches the times 1 to 14 for the sample above.
The program for Factory Machines
The program is the first-YES loop with two changes. The candidates run from 1 to , and the question at mid is answered by adding up what every machine has finished by that time.
def min_time(machines, products):
def made_by(time):
return sum(time // k for k in machines)
left, right = 1, min(machines) * products
answer = right
while left <= right:
mid = left + (right - left) // 2
if made_by(mid) >= products:
answer = mid
right = mid - 1
else:
left = mid + 1
return answer
n, t = map(int, input().split())
machines = list(map(int, input().split()))
print(min_time(machines, t))On the sample the program prints 8.
With the largest input the range ends at , and each probe divides by all machine times:
The three steps of a search on the answer
Factory Machines took three decisions, and every search on the answer takes the same three:
- Say what a candidate is, and write the check for one candidate. For Factory Machines a candidate is a time, and the check adds up the products finished by then.
- Make sure the check is monotone, with an argument about the problem. Trying a few values is not enough. For Factory Machines the argument was that more time never lowers the total.
- Find a first candidate below which nothing can work and a last candidate that certainly works, and run the first-YES loop between them.
The next problem looks different and has the same three steps. Try to name the candidate and the check before you read past the card.
There are piles of bananas, pile holding piles[i], and hours. Each hour Koko picks one pile and eats bananas from it, or the whole pile if it has fewer than ; she never moves to a second pile in the same hour. Return the smallest whole number that lets her finish every pile within hours.
Constraints
-
piles.length piles.length-
piles[i]
Sample 1 · Input
piles = [3,6,7,11], h = 8
Output
4
Sample 2 · Input
piles = [30,11,23,4,20], h = 5
Output
30
Sample 3 · Input
piles = [30,11,23,4,20], h = 6
Output
23
In the first sample, at speed 4 the piles of 3, 6, 7 and 11 bananas take 1, 2, 2 and 3 hours, which is 8 hours and just in time. At speed 3 they take 1, 2, 3 and 4 hours, 10 in all, which is too slow. So the answer is 4.
A candidate is a speed . A pile of bananas takes hours, rounded up because the last hour on a pile may be a partial one. The check adds up the hours and says YES if they fit:
With whole numbers, is (p + k - 1) // k: adding before the division lifts any pile with a remainder into the next hour and leaves an exact multiple where it was.
The check is monotone because eating faster never makes a pile take longer. Once a speed is fast enough, every higher speed is too. For the range, speed 1 is the slowest speed there is, and speed certainly works: every pile then takes one hour, and is guaranteed to be at least the number of piles.
def min_eating_speed(piles, h):
def hours(speed):
return sum((p + speed - 1) // speed for p in piles)
left, right = 1, max(piles)
answer = right
while left <= right:
mid = left + (right - left) // 2
if hours(mid) <= h:
answer = mid
right = mid - 1
else:
left = mid + 1
return answer
print(min_eating_speed([3, 6, 7, 11], 8), min_eating_speed([30, 11, 23, 4, 20], 6))The program prints 4 and 23, the answers to the first and third samples.
On the first sample the loop probes speed 6 (6 hours, YES), speed 3 (10 hours, NO) and speed 4 (8 hours, YES), and returns 4.
Search for the largest answer that works
Both problems so far asked for the smallest candidate that works, and their answers read NO, ..., NO, YES, ..., YES. When a problem asks for the largest value that works, the picture is mirrored: the small candidates work and the large ones fail.
There are baskets at the distinct positions position[i] on a line, and balls. Put the balls into different baskets so that the smallest distance between any two balls is as large as possible, and return that distance.
Constraints
-
position[i]
Sample 1 · Input
position = [1,2,3,4,7], m = 3
Output
3
Sample 2 · Input
position = [5,4,3,2,1,1000000000], m = 2
Output
999999999
In the first sample, putting the three balls in the baskets at 1, 4 and 7 keeps every two of them at least 3 apart. No choice of baskets keeps them 4 apart: three balls 4 apart need the first and the last to be at least 8 apart, and the baskets only reach from 1 to 7.
A candidate is a distance , and the check asks whether the balls can be placed so that every two are at least apart. If they can, the same placement also keeps them apart, so every smaller distance works too. The answers read YES, ..., YES, NO, ..., NO, and the problem wants the last YES.
The loop for the last YES mirrors the first-YES loop. A YES at mid is saved, and a larger candidate might work as well, so the search goes on to the right: left = mid + 1. A NO rules out mid and every larger candidate: right = mid - 1.
That leaves the check: for one distance , can balls be placed? Sort the basket positions and go through them from left to right. Put the first ball in the first basket. After that, put a ball in each basket that is at least past the last ball placed, and count the balls. If the count reaches , the check says YES.
Trying this one placement is enough. Call it ours, and call any other placement that keeps every two balls at least apart theirs. Ball by ball from the left, ours is never to the right of theirs. Our first ball is in the first basket, so it is not to the right of their first ball.
Now say our -th ball is not to the right of their -th ball. Their next ball is at least past their -th ball, so it is also at least past ours. Our rule takes the first basket that is at least past our last ball, so our next ball goes into the basket of their next ball or an earlier one, and it is not to the right of theirs either. Each of our balls is at or to the left of the matching ball of theirs, so if they place balls, so do we. When ours places fewer than , no placement can, and the check says NO.
For the range, distance 1 always works, because the baskets are at distinct whole-number positions and there are at least of them. No distance larger than the distance between the first and the last basket can work, so the range ends there.
def max_distance(position, m):
position = sorted(position)
def fits(gap):
count, last = 1, position[0]
for p in position[1:]:
if p - last >= gap:
count += 1
last = p
return count >= m
left, right = 1, position[-1] - position[0]
answer = 1
while left <= right:
mid = left + (right - left) // 2
if fits(mid):
answer = mid
left = mid + 1
else:
right = mid - 1
return answer
print(max_distance([1, 2, 3, 4, 7], 3), max_distance([5, 4, 3, 2, 1, 1000000000], 2))The program prints 3 and 999999999, the answers to the two samples.
On the first sample the range is 1 to 6. The loop probes distance 3 (balls at 1, 4 and 7, YES), then 5 and 4 (only the balls at 1 and 7 fit, NO), and returns 3.
How many checks a search on the answer takes
- Search on the answer
- About probes over a range of candidates, each one a check that costs .
- Factory Machines
- About 60 probes of divisions each: steps.
- Koko Eating Bananas
- About 30 probes over piles: steps.
- Magnetic Force
- One sort, then about 30 probes over baskets: steps.
- Trying every candidate
- Up to checks for Factory Machines.
Common mistakes when searching on the answer
Starting a speed or capacity search at 0.
- Where it breaks
- Koko Eating Bananas with
left = 0, piles[3]and probes speed 1, a YES, and then speed 0, where the division raisesZeroDivisionErrorin Python and is undefined behavior in C++. - The fix
- Start at the smallest candidate that makes sense, speed 1.
Using a fixed upper bound of and letting the check add without limit in C++.
- Where it breaks
- With 200,000 one-second machines, the first probe near totals about products, past the signed 64-bit limit of about . That overflow is undefined behavior in C++.
- The fix
- Use
right = min(k) * t, or stop adding as soon as the total reaches .
Moving left after a YES when the problem wants the last YES.
- Where it breaks
- Magnetic Force on
[1, 2, 3, 4, 7]with probes distance 3, a YES, then goes left and probes distance 1, also a YES, and returns 1 where the answer is 3. - The fix
- Write down the order of the answers first. For YES, ..., YES, NO, ..., NO, a YES moves
lefttomid + 1.
Recall Packages with given weights must be shipped in their given order within $d$ days, and each day's load may not exceed the truck's capacity. You want the smallest capacity that is enough. What is a candidate, why is the check monotone, and what range do you search?
A candidate is a capacity. The check loads the packages in order, starts a new day whenever the next package would not fit, and says YES if it used at most days. It is monotone because a larger truck never needs more days. The range starts at the heaviest package, since a smaller truck cannot carry it at all, and ends at the sum of all weights, which ships everything in one day.
For the weights 1 to 10 and , the range is 10 to 55 and the first YES is 15.