765. Ribbons Cut to One Length
You have n ribbons, the i-th of length a[i]. You need k ribbons of the SAME integer
length to hand out. A ribbon may be cut into as many pieces as you like, cuts are free, and
leftover scraps are thrown away. Ribbons may not be joined together.
Print the greatest length L for which k pieces of length L can be produced. If no positive
length works, print 0.
a = 9 7 5 3, k = 5 answer 3 3 + 2 + 1 + 1 = 7 pieces of length 3
a = 4 4 4 4 4, k = 5 answer 4 one whole ribbon each
a = 1 2 3, k = 10 answer 0 only 6 units of ribbon exist in total
a = 2 9 4 6, k = 1 answer 9 the longest ribbon, uncut
## Why this is not problem 260 and not problem 251
#251 and #260 partition a sequence whose ORDER is fixed, and every element must be used. Here the ribbons are independent, order is meaningless, and waste is allowed. That changes the feasibility test completely: there is no sweep and no accumulator, just a division per ribbon.
It is worth seeing a problem in this family where the greedy is a single line, because it makes clear that the binary search is the transferable part and the greedy is the problem-specific part.
## Testing a candidate
A ribbon of length a[i] yields a[i] / L pieces of length L, integer division, and that is
the most it can yield: a[i] / L + 1 pieces would need (a[i] / L + 1) * L units, which is more
than a[i]. So
feasible(L) = sum over i of (a[i] / L) >= k
There is no choice to make here, which is the cleanest possible form of "the greedy is optimal": the count is not a greedy estimate of the best cutting plan, it IS the best cutting plan, because cuts within one ribbon cannot help another ribbon.
## Why the predicate is monotone
Longer pieces are never easier to supply. Formally a[i] / L is non-increasing in L, since
L' >= L gives a[i] / L' <= a[i] / L. A sum of non-increasing terms is non-increasing, so once
the total drops below k it stays below. The lengths that work form a prefix 1 .. answer.
## The bounds
lo = 1 and hi = max(a). No piece can be longer than the longest ribbon, because a piece is
cut from a single ribbon. Starting the search at 1 rather than 0 matters: a[i] / 0 is a
division by zero, and zero is not a legal answer anyway. It is reported separately, when even
L = 1 fails.
hi = sum(a) / k is a valid upper bound too, though not always a tighter one: on a = 1 1 10
with k = 1 it gives 12 where max(a) gives 10. max(a) is the bound that explains the
problem, and mixing the two up (sum(a) alone) makes the search explore lengths no ribbon can
supply. That is harmless and costs less than it looks: sum(a) reaches 2 * 10^14 against
max(a) at 10^9, which is about 47.5 halvings instead of about 29.9, so at most 1.6 times the
probes rather than twice as many.
## The boundary that breaks a careless implementation
The answer 0 is not inside the search range. A loop written as
lo = 1, hi = max(a), best = 0
while lo <= hi:
mid = (lo + hi) / 2
if feasible(mid): best = mid; lo = mid + 1
else: hi = mid - 1
print best
handles it correctly because best starts at 0 and is never written when nothing is feasible.
A loop that instead returns lo returns 1 on the impossible case, which is wrong, and every
small test where the answer happens to exist still passes.
## Overflow
2 * 10^5 ribbons of length 10^9 divided by L = 1 produce 2 * 10^14 pieces. k itself
reaches 10^9. Both the accumulator and k need 64 bits. A 32-bit accumulator wraps negative
and reports the largest length as infeasible, so the answer comes out far too small on exactly
the inputs that look easiest.
## A sibling worth knowing about
The same question with REAL lengths, where the answer need not be an integer, is a different problem: the search runs on doubles for a fixed number of halvings instead of on integers. The integer form is this one; keep the distinction in mind when a statement says "length" without saying "integer".
## Cost
Time O(n log(max a)). Space O(1) beyond the input.
Constraints - `1 ≤ n ≤ 200000` - `1 ≤ k ≤ 10^9` - `1 ≤ a[i] ≤ 10^9`
Input
The first line contains two integers n and k.
The second line contains n ribbon lengths.
Output
Print one integer on its own line: the greatest length of which k equal pieces can be
cut. Print 0 if no positive length works. No other text.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.