754. The Workshop Clears the Yard

A workshop has n mechanics. Mechanic i has a rank r[i], and a mechanic of rank r needs r * k * k minutes to repair k cars. All the mechanics work at the same time and any mechanic may repair any car.

Print the fewest minutes needed to repair cars cars.

ranks 4 2 3 1, cars = 10 -> 16 ranks 5 1 8, cars = 6 -> 16 ranks 2 2 2, cars = 4 -> 8 ranks 2 2 2, cars = 3 -> 2

With ranks 4 2 3 1 and 16 minutes available the mechanics manage 2, 2, 2 and 4 cars, which is 10. With 15 minutes they manage 1, 2, 2 and 3, which is 8.

## What a candidate answer buys you

Fix a number of minutes T. Mechanic i can repair k cars inside it exactly when r[i] * k * k <= T, so the most that mechanic manages is

k = floor(sqrt(T / r[i])) with T / r[i] itself rounded down first

Rounding T / r down before taking the square root is safe because k * k is a whole number: k * k <= T / r and k * k <= floor(T / r) say the same thing.

Add those across the mechanics and compare with cars. That is the whole check, and it runs in O(n).

## Why the predicate is monotone

More minutes never means fewer cars. floor(T / r) is non-decreasing in T, and integer square root is non-decreasing in its argument, so each mechanic's count is non-decreasing and so is the total. Feasible values of T therefore form a suffix, and the earliest one is what binary search returns.

The story also makes it obvious: whatever schedule finishes in T minutes still finishes if you are given T + 1.

## The bounds

lo = 1, since cars >= 1.

hi = min(r) * cars * cars. The single best mechanic repairs every car within that, so it is certainly enough. With min(r) = 100 and cars = 10^6 that is 10^14, which is the real size of the search space and the reason a linear scan is impossible.

## The boundary that breaks a careless implementation

The square root, though not for the reason people usually give.

At this problem's sizes sqrt() is exact. The argument q = T / r never exceeds hi, which is 10^14; an IEEE double represents every integer up to 2^53 = 9007199254740992 exactly, and the IEEE square root is correctly rounded, so (long long) sqrt((double) q) lands on the right integer everywhere in that range. Probing k * k + d for d in -2 .. 2 all the way up to 10^14 finds no disagreement at all with an exact integer root.

Write the repair loops anyway:

k = (long long) sqrt((double) q) while (k > 0 && k * k > q) k -= 1 while ((k + 1) * (k + 1) <= q) k += 1

They are insurance that costs nothing. At these bounds each loop body runs zero times, so the pair adds two comparisons per call, and in return the count no longer depends on q staying under 2^53. That dependence is real, just not here: once the argument passes 2^53 it is no longer exactly representable as a double and the cast genuinely does come back one out. Problem 248 takes the integer square root at 10^18, more than a hundred times past 2^53, and there the repair is not insurance but the whole point.

## Overflow

hi itself is 10^14, so it must be built in 64-bit arithmetic: writing min_r * cars * cars with 32-bit values wraps before it is ever assigned. (k + 1) * (k + 1) inside the repair loop reaches 10^14 as well. The car count needs an early exit for the same reason as problem 753.

## Related problems

Problem 753 is this with a rate that never changes, so the count is a division instead of a square root. Problem 758 sits between them: its cumulative cost r * j * (j + 1) / 2 is quadratic in j as well, and only the MARGINAL cost of one more dish is linear, so the count there is the root of a triangular number rather than the root of a square. Problem 248 is where the integer square root itself is taught.

## Cost

Time O(n log(min(r) * cars^2)). Space O(n).

Constraints - `1 ≤ n ≤ 100000` - `1 ≤ cars ≤ 10^6` - `1 ≤ r[i] ≤ 100`