Editorial for WC '16 Finals S3 - Privacy
Submitting an official solution before solving the problem yourself is a bannable offence.
This problem can be solved with dynamic programming. Let be the minimum number of treats required to satisfy the first
cows (cows
) while dividing them into
troughs. The base case is
, and the final answer will be
, as we'll be installing
dividers to divide the
cows into
troughs.
From a given state , the only choice is regarding how many cows should be included in the next trough. The first cow in the trough will be
, and the last will be
(for some
between
and
, inclusive). We should consider each possible value of
. For a given
, there will be
cows in the next trough. The number of treats
required to satisfy each of those
cows can easily be computed by iterating over them (and comparing their
values to the cow count
). We end up with the transition
.
A direct implementation of the approach described above would have a time complexity of – we'll consider each of the
states in turn (for
from
to
and from
from
to
), consider each of the
possible transitions from it, and then compute each transition's
cost in another
time. This is too slow to earn full marks. However, the time complexity can be improved to
by essentially just swapping the nesting order of the
and
loops. Note that each transition's
cost depends only on
and
, so there's no need to recompute it
times for all possible values of
.
Comments