Digital Logarithm (Codeforces 1728C)
Tags: 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:   pick some integer $$$i$$$ from $$$1$$$ to $$$n$$$;  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: 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: For each testcase, print the smallest number of operations required to make $$$a$$$ and $$$b$$$ similar to each other.

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$$$.

Sample Inputs:
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

Sample Outputs:
2
0
2
18

Solution (Python):
def solve():
    n = int(input())
    a = sorted(list(map(int, input().split())), reverse=True)
    b = sorted(list(map(int, input().split())), reverse=True)
    cnta = [0] * 9
    cntb = [0] * 9
    answ = i = j = 0
    while i < len(a) and j < len(b):
        if a[i] == b[j]:
            i += 1
            j += 1
        elif a[i] > b[j]:
            if a[i] >= 10:
                t = len(str(a[i]))
                answ += 1
            else:
                t = a[i]
            cnta[t - 1] += 1
            i += 1
        else:
            if b[j] >= 10:
                t = len(str(b[j]))
                answ += 1
            else:
                t = b[j]
            cntb[t - 1] += 1
            j += 1
    n = len(a)
    if i < n:
        for q in range(i, n):
            if a[q] >= 10:
                t = len(str(a[q]))
                answ += 1
            else:
                t = a[q]
            cnta[t - 1] += 1
    if j < n:
        for q in range(j, n):
            if b[q] >= 10:
                t = len(str(b[q]))
                answ += 1
            else:
                t = b[q]
            cntb[t - 1] += 1
    for i in range(1, 9):
        answ += abs(cnta[i] - cntb[i])
    print(answ)
    return
t = int(input())
for i in range(t):
    solve()

Solution (Python):
import collections
for _ in range(int(input())):
    n = int(input())
    a = input().split()
    b = collections.Counter(input().split())
    ops = 0
    newa = []
    newb = {}
    for i in range(len(a)):
        if a[i] in b:
            b[a[i]] -= 1
            if not b[a[i]]:
                del b[a[i]]
        elif int(a[i]) > 9:
            ops += 1
            newa.append(str(len(a[i])))
        else:
            newa.append(a[i])
    for k in b:
        if int(k) > 9:
            ops += b[k]
            l = str(len(k))
            newb[l] = (newb[l] if l in newb else 0) + b[k]
        else:
            newb[k] = (newb[k] if k in newb else 0) + b[k]
    for i in range(len(newa)):
        if newa[i] in newb:
            newb[newa[i]] -= 1
            if not newb[newa[i]]:
                del newb[newa[i]]
        elif int(newa[i]) > 1:
            ops += 1
    for k in newb:
        if int(k) > 1:
            ops += newb[k]
    print(ops)

Solution (Python):
ot = []
for _ in range(int(input())):
    n = int(input())
    l1 = list(map(int, input().split()))
    l2 = list(map(int, input().split()))
    d1_digits = {1: 0, 2: 0, 3: 0, 4: 0, 5: 0, 6: 0, 7: 0, 8: 0, 9: 0}
    d2_digits = {1: 0, 2: 0, 3: 0, 4: 0, 5: 0, 6: 0, 7: 0, 8: 0, 9: 0}
    d1 = {}
    d2 = {}
    out = 0
    for x in l1:
        if x == 1:
            continue
        if x not in d1:
            d1[x] = 1
        else:
            d1[x] += 1
    for x in l2:
        if x == 1:
            continue
        if x in d1:
            d1[x] -= 1
            if d1[x] == 0:
                del d1[x]
        elif x not in d2:
            d2[x] = 1
        else:
            d2[x] += 1
    for (x, y) in d1.items():
        k = len(str(x))
        if k == 1:
            d1_digits[x] += y
        else:
            d1_digits[k] += y
            out += y
    for (x, y) in d2.items():
        k = len(str(x))
        if k == 1:
            d2_digits[x] += y
        else:
            d2_digits[k] += y
            out += y
    for (x, y) in d1_digits.items():
        m = min(y, d2_digits[x])
        out += y - m + (d2_digits[x] - m)
    ot.append(str(out))
print('\n'.join(ot))