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 represent the optimal solution for a given type of question. In the optimal solution, we will pair the speed from Dmojistan with the speed from Pegland. Also, let represent the array of speeds of Dmojistan and let represent the array of speeds of Pegland.

To compute the minimum possible sum of times, . To prove that this is correct, consider any other assignment of pairings. You will be able to find two indices and where but . Consider the following cases:

• : then switching and won't make a difference in the final sum.
• : the original contribution of these 4 cyclists will be , and the new contribution after swapping will be , and . The final sum will become equal or smaller.
• : the original contribution of these 4 cyclists will be , and the new contribution after swapping will be , and . The final sum will become equal or smaller.
• : the original contribution of these 4 cyclists will be , and the new contribution after swapping will be , and . The final sum will become equal or smaller.
• : the original contribution of these 4 cyclists will be , and the new contribution after swapping will be , and . The final sum will become equal or smaller.
• : then switching and won't make a difference in the final sum.

Similarly, to maximize the sum of times, . We can analyze the cases in a similar fashion to the minimization question to prove that this is correct.

Complexity: 