756. The Day the Bouquets Can Be Cut
A row of n flowers is planted in a line. Flower i opens on day b[i] and stays open
afterwards. A bouquet needs k flowers that are ADJACENT in the row and all open; every flower
may be used in at most one bouquet.
Print the earliest day on which m bouquets can be cut, or -1 if that day never comes.
bloom 1 10 3 10 2, m = 3, k = 1 -> 3
bloom 1 10 3 10 2, m = 3, k = 2 -> -1
bloom 7 7 7 7 12 7 7, m = 2, k = 3 -> 12
bloom 1 2 3 4, m = 2, k = 2 -> 4
On day 3 the flowers open at positions 1, 3 and 5, which is three single-flower bouquets. With
k = 2 there are only 5 flowers and 3 bouquets would need 6, so that case is impossible from
the start.
## Counting bouquets on a given day
Given a day D, a flower is open when b[i] <= D. Walk the row once carrying the length of the
current run of open flowers; every time the run reaches k, cut a bouquet and reset the run to
zero:
run = 0, made = 0
for each flower:
if open: run += 1; if run == k: made += 1; run = 0
else: run = 0
Cutting greedily as soon as a run is long enough is optimal. A run of L open flowers yields
floor(L / k) bouquets however you slice it, and cutting from the left produces exactly that,
so no better arrangement exists.
## Why the predicate is monotone
A flower open on day D is still open on day D + 1, so the set of open flowers only grows.
Every run of open flowers on day D is contained in a run on day D + 1, so the bouquet count
is non-decreasing in D. Once enough bouquets are available they stay available, which is
exactly the suffix shape binary search needs.
This is worth stating carefully because it is the only reason the problem is not a search over arrangements: the DAY is monotone, the arrangement is not.
## The bounds
lo = min(b), hi = max(b). The answer has to be a day on which some flower opens, and no day
after the last bloom adds anything. Searching 1 .. 10^9 instead also works and costs a couple
more iterations.
## The -1 case, and the multiplication that ruins it
m bouquets of k flowers need m * k flowers, so the answer is -1 exactly when
m * k > n. Both can be 10^5, so the product reaches 10^10 and overflows a 32-bit signed
integer, wrapping to something negative. The comparison then passes, the search runs on an
impossible instance, and the program prints max(b) instead of -1. Compute that product in 64
bits, or rearrange it as m > n / k.
## The boundary that breaks a careless implementation
Resetting the run. After cutting a bouquet the run must go back to zero, not stay at k, or
k adjacent flowers get counted as two bouquets. And an unopened flower resets the run as well,
which is the difference between this problem and one about counting open flowers.
## Related problems
Problem 259 spreads items out to maximise the smallest gap, which is the other classic problem where a candidate answer is tested by one greedy sweep. This one is different in that the sweep counts groups rather than gaps.
## Cost
Time O(n log(max b)). Space O(n).
Constraints - `1 ≤ n ≤ 100000` - `1 ≤ m ≤ 100000` - `1 ≤ k ≤ 100000` - `1 ≤ b[i] ≤ 10^9`
Input
The first line contains three integers n, m and k.
The second line contains n integers b[0] ... b[n-1], the day each flower opens.
Output
Print one integer, the earliest day on which m bouquets can be cut, or -1 if it is impossible. Print it alone on one line.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.