Hero to Zero
Contest: 2022-2023 ICPC, NERC, Southern and Volga Russian Regional Contest (Online Mirror, ICPC Rules, Preferably Teams)
Difficulty rating: 2900
Tags: graph matchings, math

There are no heroes in this problem. I guess we should have named it "To Zero".

You are given two arrays $$$a$$$ and $$$b$$$, each of these arrays contains $$$n$$$ non-negative integers.

Let $$$c$$$ be a matrix of size $$$n \times n$$$ such that $$$c_{i,j} = |a_i - b_j|$$$ for every $$$i \in [1, n]$$$ and every $$$j \in [1, n]$$$.

Your goal is to transform the matrix $$$c$$$ so that it becomes the zero matrix, i. e. a matrix where every element is exactly $$$0$$$. In order to do so, you may perform the following operations any number of times, in any order:

- choose an integer $$$i$$$, then decrease $$$c_{i,j}$$$ by $$$1$$$ for every $$$j \in [1, n]$$$ (i. e. decrease all elements in the $$$i$$$-th row by $$$1$$$). In order to perform this operation, you pay $$$1$$$ coin;
- choose an integer $$$j$$$, then decrease $$$c_{i,j}$$$ by $$$1$$$ for every $$$i \in [1, n]$$$ (i. e. decrease all elements in the $$$j$$$-th column by $$$1$$$). In order to perform this operation, you pay $$$1$$$ coin;
- choose two integers $$$i$$$ and $$$j$$$, then decrease $$$c_{i,j}$$$ by $$$1$$$. In order to perform this operation, you pay $$$1$$$ coin;
- choose an integer $$$i$$$, then increase $$$c_{i,j}$$$ by $$$1$$$ for every $$$j \in [1, n]$$$ (i. e. increase all elements in the $$$i$$$-th row by $$$1$$$). When you perform this operation, you receive $$$1$$$ coin;
- choose an integer $$$j$$$, then increase $$$c_{i,j}$$$ by $$$1$$$ for every $$$i \in [1, n]$$$ (i. e. increase all elements in the $$$j$$$-th column by $$$1$$$). When you perform this operation, you receive $$$1$$$ coin.

You have to calculate the minimum number of coins required to transform the matrix $$$c$$$ into the zero matrix. Note that all elements of $$$c$$$ should be equal to $$$0$$$ simultaneously after the operations.

Input format:
The first line contains one integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^8$$$).

The third line contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$0 \le b_j \le 10^8$$$).

Output format:
Print one integer — the minimum number of coins required to transform the matrix $$$c$$$ into the zero matrix.

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

Note:
In the first example, the matrix looks as follows:

111000111

You can turn it into a zero matrix using $$$2$$$ coins as follows:

- subtract $$$1$$$ from the first row, paying $$$1$$$ coin;
- subtract $$$1$$$ from the third row, paying $$$1$$$ coin.

In the second example, the matrix looks as follows:

221001221

You can turn it into a zero matrix using $$$5$$$ coins as follows:

- subtract $$$1$$$ from the first row, paying $$$1$$$ coin;
- subtract $$$1$$$ from the third row, paying $$$1$$$ coin;
- subtract $$$1$$$ from the third row, paying $$$1$$$ coin;
- subtract $$$1$$$ from $$$a_{2,3}$$$, paying $$$1$$$ coin;
- add $$$1$$$ to the third column, receiving $$$1$$$ coin;
- subtract $$$1$$$ from the first row, paying $$$1$$$ coin;
- subtract $$$1$$$ from $$$a_{2,3}$$$, paying $$$1$$$ coin.

Example input:
3
1 2 3
2 2 2

Example output:
2

Example input:
3
3 1 3
1 1 2

Example output:
5

Editorial:
The order of operations is interchangeable, so we assume that we perform mass operations first, and operations affecting single elements last.
Suppose $$$p_i$$$ is the value we subtract from the $$$i$$$-th row using the operations affecting the whole row, and $$$q_j$$$ is the value we subtract from the $$$j$$$-th column using the operations affecting the whole column. Then the number of coins we have to pay is $$$S - (n-1) \cdot (\sum p_i + \sum q_j)$$$, since every such operation "saves" us exactly $$$n-1$$$ coins by decreasing the sum in the matrix by $$$n$$$ using only one coin.
Obviously, we want to maximize $$$\sum p_i + \sum q_j$$$, but if we subtract too much, some elements of the matrix may become negative (and it will be impossible to set them to zero using single element operations). So, for every $$$i \in [1, n]$$$ and $$$j \in [1, n]$$$, the condition $$$p_i + q_j \le c_{i,j}$$$ must hold.
Now let's take a look at how the Hungarian algorithm for assignment problem works. We can notice that the potentials in the Hungarian algorithm have the same constraints as the values $$$p_i$$$ and $$$q_j$$$ in our problem, and the sum of those potentials is maximized. So, if we apply the Hungarian algorithm to the matrix $$$c$$$, we can use the potentials as the values $$$p_i$$$ and $$$q_j$$$.
But the matrix is too large, so what should we do? We can use the fact that the maximum possible sum of potentials is equal to the optimal solution of the assignment problem, so we should solve the assignment problem in some other way. And in this particular way of constructing the matrix $$$c$$$ (where $$$c_{i,j} = |a_i - b_j|$$$), the solution of the assignment problem is simple: we need to reorder the elements of both arrays $$$a$$$ and $$$b$$$ so that the value of $$$\sum |a_i - b_i|$$$ is minimized, and it's easy to see (and to prove using exchange argument method) that sorting both arrays will give us the optimal solution.
All that's left is to calculate the sum of elements in the matrix, and that can be done if for every element in $$$a$$$, we calculate the number of elements in $$$b$$$ which are less than it, the number of elements in $$$b$$$ which are greater than it, and the sum of elements of $$$b$$$ greater than it (to quickly compute the sum of $$$|a_i - b_j|$$$ for every $$$j \in [1, n]$$$). All these values can be obtained with the help of binary search, two pointers method or some data structures.
The complexity of the solution is $$$O(n \log n)$$$.