Editorial for WC '16 Contest 2 S2 - Away Mission
Submitting an official solution before solving the problem yourself is a bannable offence.
Let's first consider the case in which . We want to assemble shirts with triples of CCC values
such that, for as few of them as possible,
, where
.
For starters, let's just consider forming pairs of the green and blue CCCs , with the goal of maximizing their resulting
values. If we consider the list of all
green/blue CCC values, the best we could ever hope to do is for the largest
of these
values to be equal to the
produced
values. As it turns out, this can always be accomplished – for example, if we pair the largest green CCC with the smallest blue CCC, the second-largest green CCC with the second-smallest blue CCC, and so on. As such, if we sort these
values and take the largest
of them, we'll get an optimal set of
values.
What remains is pairing the values against these
values, which can be done greedily. Assuming that both lists are sorted in non-decreasing order, let's iterate upwards through the
values. For a given
value, we might as well match it with the smallest remaining
value which is larger than or equal to it, if any. This can be done by maintaining a pointer into the sorted list of
values, and advancing it forwards at each step until a sufficiently large
value is reached (or until it hits the end of the array, at which point no more non-red shirts can be created).
The other case, in which , is similar – we now want to maximize the number of triples in which
. This time, we'll want to form
pairs with the goal of minimizing their resulting
values. If we consider the largest of all of the green or blue CCC values, it will necessarily need to be one of the
values. It'll need to be matched with some value from the opposite list, so we might as well pair it with the largest of those, in an effort to minimize future
values. Therefore, it's always optimal to pair the largest green and blue CCCs together, and this can be extended to show that we should always sort the lists of green and blue CCC values independently, and then pair them up in that order to compute an optimal set of
values.
At that point, we can follow a very similar algorithm to the case in order to greedily pair up the
and
values, this time iterating downwards through the
values and matching each one against the larger remaining
value which is smaller than it (if any).
The time complexity of this algorithm in either of the two cases is dependent on sorting component values. This can be done in
time, or
time if we take advantage of their limited magnitudes with radix sort.
Comments