codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1728C.md (1968B)


      1 Source: https://codeforces.com/problemset/problem/1728/C
      2 
      3 C. Digital Logarithm
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 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.
     22 
     23 You are given two arrays $a$ and $b$, each containing $n$ positive integers. In one operation, you do the following:
     24 
     25 1. pick some integer $i$ from $1$ to $n$;
     26 2. assign either $f(a_i)$ to $a_i$ or $f(b_i)$ to $b_i$.
     27 
     28 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$).
     29 
     30 What's the smallest number of operations required to make $a$ and $b$ similar to each other?
     31 
     32 Input
     33 
     34 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of testcases.
     35 
     36 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.
     37 
     38 The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \lt 10^9$).
     39 
     40 The third line contains $n$ integers $b_1, b_2, \dots, b_n$ ($1 \le b_j \lt 10^9$).
     41 
     42 The sum of $n$ over all testcases doesn't exceed $2 \cdot 10^5$.
     43 
     44 Output
     45 
     46 For each testcase, print the smallest number of operations required to make $a$ and $b$ similar to each other.
     47 
     48 Example
     49 
     50 Input
     51 
     52 ```
     53 4
     54 
     55 1
     56 
     57 1
     58 
     59 1000
     60 
     61 4
     62 
     63 1 2 3 4
     64 
     65 3 1 4 2
     66 
     67 3
     68 
     69 2 9 3
     70 
     71 1 100 9
     72 
     73 10
     74 
     75 75019 709259 5 611271314 9024533 81871864 9 3 6 4865
     76 
     77 9503 2 371245467 6 7 37376159 8 364036498 52295554 169
     78 ```
     79 
     80 Output
     81 
     82 ```
     83 2
     84 0
     85 2
     86 18
     87 ```
     88 
     89 Note
     90 
     91 In the first testcase, you can apply the digital logarithm to $b_1$ twice.
     92 
     93 In the second testcase, the arrays are already similar to each other.
     94 
     95 In the third testcase, you can first apply the digital logarithm to $a_1$, then to $b_2$.