Editorial for WC '15 Finals S2 - Hydration
Submitting an official solution before solving the problem yourself is a bannable offence.
If it's possible for the cows to all get a drink, then it must be doable in at most minutes. If it's possible for them to finish drinking in
minutes, then it must be possible for them to finish in
minutes. This means that we can binary search for the answer on the
, and if it's impossible in even
minutes, we'll get a result of
and can output
-1
instead.
What remains is being able to determine whether or not the cows can all have a drink within minutes. In particular, we would like to know if there exists a way to assign the cows to the troughs such that each trough is assigned at most
cows, and that each cow
's assigned trough
satisfies
.
If cow is shorter than cow
, then intuitively, we should never assign cow
to a taller trough than cow
because otherwise they could be swapped for a better configuration. This idea suggests a greedy algorithm.
Assuming that the heights of the cows and troughs have both been sorted in non-decreasing order (respectively doable in time complexities and
), we can iterate over each cow
in order, assigning it to the first trough
that it can validly drink from (if any). In other words, we're looking for the smallest
such that
, and fewer than
cows have been assigned to drink from trough
so far.
As we iterate from
to
, note that
will never decrease. Therefore, we only have to keep track of the current value of
and the number of cows
that have been assigned to trough
, for each cow
, we'll first increase
as long as it's invalid (resetting
to be
whenever
is increased), and then assign cow
to it (increasing
by
). If
exceeds
, then we'll know that there was no valid trough, meaning that not all of the cows can drink within
minutes. The total time complexity of this algorithm is therefore
.
Comments