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 represent the optimal solution for a given type of question. In the optimal solution, we will pair the i^{th} speed from Dmojistan with the Z[i]^{th} speed from Pegland. Also, let D represent the array of speeds of Dmojistan and let P represent the array of speeds of Pegland.

To compute the minimum possible sum of times, 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 and j where i < j but Z[i] > Z[j]. Consider the following cases:

  • P[Z[i]] \ge P[Z[j]] \ge D[j] \ge D[i]: then switching Z[i] and Z[j] won't make a difference in the final sum.
  • 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], and the new contribution after swapping will be P[Z[i]] + P[Z[j]], and 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]]: the original contribution of these 4 cyclists will be P[Z[i]] + D[j], and the new contribution after swapping will be P[Z[i]] + D[i], and 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]: the original contribution of these 4 cyclists will be D[j] + P[Z[i]], and the new contribution after swapping will be D[j] + P[Z[j]], and 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]]: the original contribution of these 4 cyclists will be D[j] + P[Z[i]], and the new contribution after swapping will be D[j] + D[i], and 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]]: then switching Z[i] and 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\}. 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)


Comments

There are no comments at the moment.