758. Cooks Who Get Slower As They Go
A kitchen must serve P identical dishes. There are k cooks. A cook with rank r takes
r minutes for the first dish, 2r for the second, 3r for the third and so on, so j
dishes take that cook
r + 2r + 3r + ... + jr = r * j * (j + 1) / 2 minutes
All the cooks work at the same time and any cook can make any dish.
Print the fewest minutes in which P dishes are served.
ranks 1 2 3 4, P = 10 -> 12
ranks 4 3 8, P = 8 -> 24
ranks 1 1, P = 2 -> 1
ranks 1 1, P = 3 -> 3
With ranks 1 2 3 4 and 12 minutes the cooks manage 4, 3, 2 and 2 dishes, which is 11. The
rank-4 cook gets two rather than one because 4 + 8 = 12, exactly the time available. That is
more than the ten required, so the answer being 12 has to come from the other side: at 11 minutes
the counts are 4, 2, 2 and 1, which is 9. The total jumps from 9 to 11 without passing through 10,
because a cook's count rises in steps, and the answer is the first minute at which it reaches the
target rather than the minute at which it equals it.
## Why this is not the constant-rate problem
Problem 753 has cooks who never slow down, so the count by minute T is one division. Here the
j-th dish costs more than the one before it, so the count is the largest j with
r * j * (j + 1) / 2 <= T
which is a quadratic, not a division. Everything else about the method is the same, and that is the point of reading the two together.
## Solving the quadratic without a loop
Write x = T / r, rounded down, which is legitimate because j * (j + 1) / 2 is a whole number.
Solving j * (j + 1) / 2 <= x gives
j = floor((sqrt(1 + 8x) - 1) / 2)
Repair that value rather than trusting it. The root itself is exact at these sizes, because
1 + 8x never passes 4004001 and a double holds every integer up to 2^53 exactly. But the
formula is a subtraction, a division and a truncation stacked on top of the root, and the floor
of a value sitting right on an integer is precisely where a last-bit difference changes the
answer. So do what problem 754 does: treat the formula as an estimate and fix it with two short
loops that push j up while the next triangle still fits and down while the current one does
not. When the estimate is already right, which it usually is, the pair costs two comparisons.
Counting j with a loop instead is correct, and at these constraints it is even fast enough,
because no cook ever makes more than P = 1000 dishes. The reason to solve the quadratic is that
a loop's cost is set by the ANSWER's size rather than the input's, and that bill comes due the
moment the bounds grow. The same shape in problem 754, where one mechanic can repair 10^6 cars,
makes the inner loop 10^6 iterations deep for every worker on every search step. Closed form
first; loop only to repair it.
## Why the predicate is monotone
Each cook's dish count is the largest j satisfying an inequality whose right-hand side is T.
Enlarging T can only admit more values of j, never fewer, so every cook's count is
non-decreasing and so is the total. More time never means fewer dishes, so the feasible minutes
form a suffix.
## The bounds
lo = 1. hi = min(r) * P * (P + 1) / 2, the time the single fastest cook needs to make every
dish alone. With r and P both at 1000 that is about 5 * 10^8.
## Why nothing here overflows, and how you would know
Do the arithmetic rather than guessing in either direction. Every input value is at most 1000, so
hi = min(r) * P * (P + 1) / 2 is at most 1000 * 1000 * 1001 / 2 = 500500000, and even the
intermediate product 1000 * 1000 * 1001 = 1001000000 stays under the 32-bit signed ceiling of
2147483647.
Inside the count, x = T / r is at most P * (P + 1) / 2 = 500500, because T never exceeds
min(r) * P * (P + 1) / 2 and r is never below min(r). So 1 + 8x is at most 4004001,
three orders of magnitude below the 32-bit limit, and (j + 1) * (j + 2) / 2 with j never
above P = 1000 is at most 501501.
Nothing in this problem needs 64 bits. Reaching that conclusion by bounding each expression
against the constraints is the point; the identical code in problem 754, where cars reaches
10^6 and hi reaches 10^14, does need them, and the only way to tell the two apart is to
work it out.
## The boundary that breaks a careless implementation
P = 1 with several cooks: the answer is min(r), not the sum of anything. And a cook whose
rank exceeds T must contribute zero, which the formula gives correctly only if x is computed
as T / r with integer division rather than T divided by a float.
## Cost
Time O(k log(min(r) * P^2)). Space O(k).
Constraints - `1 ≤ k ≤ 1000` - `1 ≤ P ≤ 1000` - `1 ≤ r[i] ≤ 1000`
Input
The first line contains two integers k and P, the number of cooks and the number of dishes.
The second line contains k integers r[0] ... r[k-1], the ranks of the cooks.
Output
Print one integer, the fewest minutes in which all P dishes are served. Print it alone on one line, with no units.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.