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.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
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:
Comments