Editorial for CCC '16 S2 - Tandem Bicycle - DMOJ: Modern Online Judge

Editorial for CCC '16 S2 - Tandem Bicycle

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.

Author: FatalEagle

First, we will sort both arrays of speeds in nondecreasing order. Let the array $Z$ ~Z~ represent the optimal solution for a given type of question. In the optimal solution, we will pair the $i^{th}$ ~i^{th}~ speed from Dmojistan with the $Z[i]^{th}$ ~Z[i]^{th}~ speed from Pegland. Also, let $D$ ~D~ represent the array of speeds of Dmojistan and let $P$ ~P~ represent the array of speeds of Pegland.

To compute the minimum possible sum of times, $Z=\{1, 2, 3, \dots, N\}$ ~Z=\{1, 2, 3, \dots, N\}~. To prove that this is correct, consider any other assignment of pairings. You will be able to find two indices $i$ ~i~ and $j$ ~j~ where $i < j$ ~i < j~ but $Z[i] > Z[j]$ ~Z[i] > Z[j]~. Consider the following cases:

$P[Z[i]] \ge P[Z[j]] \ge D[j] \ge D[i]$ ~P[Z[i]] \ge P[Z[j]] \ge D[j] \ge D[i]~: then switching $Z[i]$ ~Z[i]~ and $Z[j]$ ~Z[j]~ won't make a difference in the final sum.
$P[Z[i]] \ge D[j] \ge P[Z[j]] \ge D[i]$ ~P[Z[i]] \ge D[j] \ge P[Z[j]] \ge D[i]~: the original contribution of these 4 cyclists will be $P[Z[i]] + D[j]$ ~P[Z[i]] + D[j]~, and the new contribution after swapping will be $P[Z[i]] + P[Z[j]]$ ~P[Z[i]] + P[Z[j]]~, and $P[Z[j]] \le D[j]$ ~P[Z[j]] \le D[j]~. The final sum will become equal or smaller.
$P[Z[i]] \ge D[j] \ge D[i] \ge P[Z[j]]$ ~P[Z[i]] \ge D[j] \ge D[i] \ge P[Z[j]]~: the original contribution of these 4 cyclists will be $P[Z[i]] + D[j]$ ~P[Z[i]] + D[j]~, and the new contribution after swapping will be $P[Z[i]] + D[i]$ ~P[Z[i]] + D[i]~, and $D[i] \le D[j]$ ~D[i] \le D[j]~. The final sum will become equal or smaller.
$D[j] \ge P[Z[i]] \ge P[Z[j]] \ge D[i]$ ~D[j] \ge P[Z[i]] \ge P[Z[j]] \ge D[i]~: the original contribution of these 4 cyclists will be $D[j] + P[Z[i]]$ ~D[j] + P[Z[i]]~, and the new contribution after swapping will be $D[j] + P[Z[j]]$ ~D[j] + P[Z[j]]~, and $P[Z[j]] \le P[Z[i]]$ ~P[Z[j]] \le P[Z[i]]~. The final sum will become equal or smaller.
$D[j] \ge P[Z[i]] \ge D[i] \ge P[Z[j]]$ ~D[j] \ge P[Z[i]] \ge D[i] \ge P[Z[j]]~: the original contribution of these 4 cyclists will be $D[j] + P[Z[i]]$ ~D[j] + P[Z[i]]~, and the new contribution after swapping will be $D[j] + D[i]$ ~D[j] + D[i]~, and $D[i] \le P[Z[i]]$ ~D[i] \le P[Z[i]]~. The final sum will become equal or smaller.
$D[j] \ge D[i] \ge P[Z[i]] \ge P[Z[j]]$ ~D[j] \ge D[i] \ge P[Z[i]] \ge P[Z[j]]~: then switching $Z[i]$ ~Z[i]~ and $Z[j]$ ~Z[j]~ won't make a difference in the final sum.

Similarly, to maximize the sum of times, $Z=\{N, N-1, N-2, \dots, 1\}$ ~Z=\{N, N-1, N-2, \dots, 1\}~. We can analyze the cases in a similar fashion to the minimization question to prove that this is correct.

Complexity: $\mathcal{O}(N \log N)$ ~\mathcal{O}(N \log N)~

Comments

There are no comments at the moment.