Digital Logarithm
Contest: Educational Codeforces Round 135 (Rated for Div. 2)
Difficulty rating: 1400
Tags: data structures, greedy, sortings

Let's define $$$f(x)$$$ for a positive integer $$$x$$$ as the length of the base-10 representation of $$$x$$$ without leading zeros. I like to call it a digital logarithm. Similar to a digital root, if you are familiar with that.

You are given two arrays $$$a$$$ and $$$b$$$, each containing $$$n$$$ positive integers. In one operation, you do the following:

1. pick some integer $$$i$$$ from $$$1$$$ to $$$n$$$;
2. assign either $$$f(a_i)$$$ to $$$a_i$$$ or $$$f(b_i)$$$ to $$$b_i$$$.

Two arrays are considered similar to each other if you can rearrange the elements in both of them, so that they are equal (e. g. $$$a_i = b_i$$$ for all $$$i$$$ from $$$1$$$ to $$$n$$$).

What's the smallest number of operations required to make $$$a$$$ and $$$b$$$ similar to each other?

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of testcases.

The first line of the testcase contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of elements in each of the arrays.

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

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

The sum of $$$n$$$ over all testcases doesn't exceed $$$2 \cdot 10^5$$$.

Output format:
For each testcase, print the smallest number of operations required to make $$$a$$$ and $$$b$$$ similar to each other.

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

Note:
In the first testcase, you can apply the digital logarithm to $$$b_1$$$ twice.

In the second testcase, the arrays are already similar to each other.

In the third testcase, you can first apply the digital logarithm to $$$a_1$$$, then to $$$b_2$$$.

Example input:
4
1
1
1000
4
1 2 3 4
3 1 4 2
3
2 9 3
1 100 9
10
75019 709259 5 611271314 9024533 81871864 9 3 6 4865
9503 2 371245467 6 7 37376159 8 364036498 52295554 169

Example output:
2
0
2
18

Editorial:
First, why can you always make the arrays similar? Applying a digital logarithm to any number will eventually make it equal to $$$1$$$. Thus, you can at least make all numbers into $$$1$$$s in both arrays.
Then notice the most improtant thing — applying the digital logarithm to a number greater than $$$1$$$ always makes this number smaller.
Thus, if a number appears in only one of the arrays, you will have to do one of the followings two things:
• decrease some greater number to make it equal to this one;
• decrease this number.
What if there is no greater number at all? This is the case for the largest number in both arrays altogether. If it appears in only one of the arrays, you must always decrease. If it appears in both, though, why decrease it further? Worst case, you will decrease it in one array, then you'll have to decrease it in the other array as well. This is never more optimal than just matching one occurrence in both arrays to each other and removing them from the arrays.
So, the proposed solution is the following. Consider the largest element in each array. If they are equal, remove both. If not, apply digital logarithm to the larger of them. Continue until the arrays are empty.
What's the estimated complexity of this algorithm? Each number in the first array will be considered at most the number of times you can decrease it with a digital logarithm operation plus one. That is at most $$$2+1$$$ — a number greater than $$$9$$$ always becomes a single digit and a single digit always becomes $$$1$$$. Same goes for the second array. So the complexity is basically linear.
To implement it efficiently, you will have to use some data structure that provides three operations:
• peek at the maximum;
• remove the maximum;
• insert a new element.
The perfect one is a heap — priority_queue in C++.
Overall complexity: $$$O(n \log n)$$$ per testcase.