Equal multisets | Practice Problems

Equal multisets

★★★★★

4

99 votes

Ad-Hoc, Basic Math, Easy, 簡単, Mathematics, Mathematics

Details

Problem

You are given two multisets $A$ and $B$ , each containing $N$ elements. In one step, you can choose an integer $x$ from $A$ , delete an occurrence of $x$ from $A$ , and add either $x+1$ or $x - 1$ to $A$ . Determine the minimum number of moves required such that the condition $A = B$ satisfies.

Input format

First line: Integer $N$ $(1 \le N \le 10^5)$
Second line: $N$ integers that represent the multiset $A$
Third line: $N$ integers that represent the multiset $B$

Note: All the numbers are positive integers smaller or equal to $2^{63} - 1$ .

Output format

Print the remainder of the answer when divided by $10^9 + 7$ .

Sample Input

3
4 1 3
2 6 2

Sample Output

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

To obtain the optimal answer we need to perform the following operations:

1. Delete $1$ and add $2$ , $A = \{ 2, 3, 4 \}$

2. Delete $3$ and add $2$ , $A = \{ 2, 2, 4 \}$

3. Delete $4$ and add $5$ , $A = \{ 2, 2, 5 \}$

4. Delete $5$ and add $6$ , $A = \{ 2, 2, 6 \}$

Contributers:

Gabriel Cojocaru