Editorial for WC '17 Finals S1 - An Interspecific Army
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
To minimize , it turns out that it's always optimal to pair the worst cow with the worst monkey, the second-worst cow with the second-worst monkey, and so on. To prove this, let's consider a pair of cows with combat skill levels
and
(such that
), and a pair of monkeys with combat skill levels
and
(such that
). We note that forming the pairs
and
can never be better than forming the pairs
and
. In other words,
.
Having made this insight, we'll want to sort the two lists and
in non-decreasing order, which can be done in
time. We can then simply find and output the maximum value of
over
.
Comments