Gambling
Contest: Codeforces Round 508 (Div. 2)
Difficulty rating: 1300
Tags: greedy, sortings

Two players A and B have a list of $$$n$$$ integers each. They both want to maximize the subtraction between their score and their opponent's score.

In one turn, a player can either add to his score any element from his list (assuming his list is not empty), the element is removed from the list afterward. Or remove an element from his opponent's list (assuming his opponent's list is not empty).

Note, that in case there are equal elements in the list only one of them will be affected in the operations above. For example, if there are elements $$$\{1, 2, 2, 3\}$$$ in a list and you decided to choose $$$2$$$ for the next turn, only a single instance of $$$2$$$ will be deleted (and added to the score, if necessary).

The player A starts the game and the game stops when both lists are empty. Find the difference between A's score and B's score at the end of the game, if both of the players are playing optimally.

Optimal play between two players means that both players choose the best possible strategy to achieve the best possible outcome for themselves. In this problem, it means that each player, each time makes a move, which maximizes the final difference between his score and his opponent's score, knowing that the opponent is doing the same.

Input format:
The first line of input contains an integer $$$n$$$ ($$$1 \le n \le 100\,000$$$) — the sizes of the list.

The second line contains $$$n$$$ integers $$$a_i$$$ ($$$1 \le a_i \le 10^6$$$), describing the list of the player A, who starts the game.

The third line contains $$$n$$$ integers $$$b_i$$$ ($$$1 \le b_i \le 10^6$$$), describing the list of the player B.

Output format:
Output the difference between A's score and B's score ($$$A-B$$$) if both of them are playing optimally.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example, the game could have gone as follows:

- A removes $$$5$$$ from B's list.
- B removes $$$4$$$ from A's list.
- A takes his $$$1$$$.
- B takes his $$$1$$$.

Hence, A's score is $$$1$$$, B's score is $$$1$$$ and difference is $$$0$$$.

There is also another optimal way of playing:

- A removes $$$5$$$ from B's list.
- B removes $$$4$$$ from A's list.
- A removes $$$1$$$ from B's list.
- B removes $$$1$$$ from A's list.

The difference in the scores is still $$$0$$$.

In the second example, irrespective of the moves the players make, they will end up with the same number of numbers added to their score, so the difference will be $$$0$$$.

Example input:
2
1 4
5 1

Example output:
0

Example input:
3
100 100 100
100 100 100

Example output:
0

Editorial:
This problem was greedy.
First, it is obvious that both the players will try to either take their own maximum value or remove the opponent's maximum value. Hence, the arrays should be sorted and two pointers should be maintained to keep track of how many elements from each array have been counted/removed already.
In every move, if the person has a choice to either take his own value $$$A$$$ or remove his opponent's value $$$B$$$, then he will make the choice dependent on the values of $$$A$$$ and $$$B$$$. In fact, it turns out that it is optimal just to select the choice with a greater number (in case of tie any will do).
How to prove it? One can show by induction that it does the same as the dynamic programming of size $$$n^2$$$. However, there is a more nice way.
Let's say that initially each player gets $$$0.5$$$ of all numbers in his list. This way when you choose a number from your own list you add the rest $$$0.5$$$ of it to the score. And when you remove the number from opponent's list you remove the $$$0.5$$$ of it from your opponent's score. Clearly, all moves become symmetrical to both players now! So each player can make a decision just based on which of the moves is greater.
If $$$A \gt B$$$, then he will take his number. If $$$A \lt B$$$, he will discard the opponent's number $$$B$$$. If $$$A=B$$$, he can make either of the above moves, it will not make a difference.
Complexity: $$$O(n \log n)$$$