## Editorial for Yet Another Contest 1 P1 - Mixed Doubles

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: Josh

In this editorial, let us refer to training a person and increment their skill level as a 'move'.

Let denote the sum of skill levels of all pairs at any point in time. Our aim is to maximise .

First, let's say that we have already chosen which people we will train, so we know the final skill level of each person. How can we determine the optimal pairing of the players? Applying the rearrangement inequality, we can see that is maximised when we pair the most skilled man with the most skilled woman, the second most skilled man with the second most skilled woman, and so on. This is sufficient to solve subtask 1.

Time complexity:

Note that the order of our moves doesn't matter. Let's say that we have already paired the men and women optimally, and we have already chosen the final skill levels of all the men - all that's left is to allocate the remaining minutes to the women. Every time we train a woman, increases by the skill level of that woman's partner. Hence, an optimal solution would be to allocate all remaining moves to the partner of the most skilled man.

By symmetry, if the skill levels of all of the women have been determined, and the remaining moves need to be allocated to the men, it would be optimal to allocate all remaining moves to the partner of the most skilled woman. Combining these observations, we see that there always exists an optimal solution where we only train the man with the highest initial skill level, and the woman with the highest initial skill level. (This also relies on the fact that if we only train the most skilled man, then that man will always remain the most skilled man, with the same being true for the women.)

Therefore, we have reduced the original problem to the following problem:

Given two sequences initially sorted in descending order, and , performing operations incrementing either or to maximise the value of .

As and are never modified, is never changed. Thus, we only need to maximise the value of after performing total increments. All that remains is to determine how many times to increment and how many times to increment .

For subtask 2, since is small, we can brute force over how many times to increment , with the remaining moves being used to increment .

Time complexity:

Whenever we increment , we also increase by . Similarly, whenever we increment , we also increase by .

To maximise after move, we should therefore increment whichever of or is lowest. It's not too hard to see that the greedy strategy to always increment whichever of or is lowest also maximises in the long run (try to prove it yourself)!

We can't explicitly simulate performing each move one at a time, so we will instead rely on casework.

Without loss of generality, we can assume (if not, we can just switch them around). There are two cases:

1. If , then we perform all our moves incrementing .
2. Otherwise, increment by so that . Then, we can perform half of the remaining moves incrementing (rounding up or down if necessary), and the rest of the moves incrementing .

Time complexity: