Arrays and searching 0/120

Binary search · 3 of 3

Search on the answer

Binary search over the possible answers to a problem, such as times, speeds and distances, with a check that says whether one answer works.

2,340 words · 11 min read

Part 1 of 6 Search on the answer

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 nn machines, and machine ii takes kik_i 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 tt products in total?

The first input line holds nn and tt, and the second line holds k1,…,knk_1, \dots, k_n. Print the shortest time.

Constraints

  • 1≤n≤2⋅1051 \le n \le 2 \cdot 10^5
  • 1≤t≤1091 \le t \le 10^9
  • 1≤ki≤1091 \le k_i \le 10^9

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 kk seconds finishes a product at times kk, 2k2k, 3k3k and so on, so by time TT it has finished ⌊T/k⌋\lfloor T / k \rfloor products, which is T/kT / k rounded down. A product that is still being made does not count. The table adds this up for the times 5 to 10.

Products finished by time T on machines that take 3, 2 and 5 seconds
Time TT3-second machine2-second machine5-second machineTotalAt least 7?
51214NO
62316NO
72316NO
82417YES
93418YES
1035210YES

The total first reaches 7 at time 8, so the answer is 8.

The direct way to find that time is to try T=1,2,3,…T = 1, 2, 3, \dots in order and stop at the first total that reaches the tt products wanted, 7 in the sample. Each try adds up one division per machine, nn in all, and the number of tries is the answer itself. With a single machine that needs 10910^9 seconds per product and 10910^9 products wanted, the answer is 101810^{18}, so this loop can take 101810^{18} tries.

Now read the last column from top to bottom: NO, NO, NO, YES, YES, YES. The question "have the machines finished at least tt products by time TT?" 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 tt it never falls below tt 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.