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.

To minimize D, 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 C_1 and C_2 (such that C_1 < C_2), and a pair of monkeys with combat skill levels M_1 and M_2 (such that M_1 < M_2). We note that forming the pairs (C_1, M_2) and (C_2, M_1) can never be better than forming the pairs (C_1, M_1) and (C_2, M_2). In other words, \max(|C_1-M_2|, |C_2-M_1|) \ge \max(|C_1-M_1|, |C_2-M_2|).

Having made this insight, we'll want to sort the two lists C_1, \dots, C_N and M_1, \dots, M_N in non-decreasing order, which can be done in \mathcal O(N \log N) time. We can then simply find and output the maximum value of |C_i-M_i| over i = 1 \dots N.


There are no comments at the moment.