codeforces-scrape

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

1573B.md (2347B)


      1 Source: https://codeforces.com/problemset/problem/1573/B
      2 
      3 B. Swaps
      4 
      5 time limit per test
      6 
      7 1 second
      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 You are given two arrays $a$ and $b$ of length $n$. Array $a$ contains each odd integer from $1$ to $2n$ in an arbitrary order, and array $b$ contains each even integer from $1$ to $2n$ in an arbitrary order.
     22 
     23 You can perform the following operation on those arrays:
     24 
     25 * choose one of the two arrays
     26 * pick an index $i$ from $1$ to $n-1$
     27 * swap the $i$-th and the $(i+1)$-th elements of the chosen array
     28 
     29 Compute the minimum number of operations needed to make array $a$ lexicographically smaller than array $b$.
     30 
     31 For two different arrays $x$ and $y$ of the same length $n$, we say that $x$ is lexicographically smaller than $y$ if in the first position where $x$ and $y$ differ, the array $x$ has a smaller element than the corresponding element in $y$.
     32 
     33 Input
     34 
     35 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$).
     36 
     37 The first line of each test case contains a single integer $n$ ($1 \le n \le 10^5$) — the length of the arrays.
     38 
     39 The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 2n$, all $a_i$ are odd and pairwise distinct) — array $a$.
     40 
     41 The third line of each test case contains $n$ integers $b_1, b_2, \ldots, b_n$ ($1 \le b_i \le 2n$, all $b_i$ are even and pairwise distinct) — array $b$.
     42 
     43 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.
     44 
     45 Output
     46 
     47 For each test case, print one integer: the minimum number of operations needed to make array $a$ lexicographically smaller than array $b$.
     48 
     49 We can show that an answer always exists.
     50 
     51 Example
     52 
     53 Input
     54 
     55 ```
     56 3
     57 2
     58 3 1
     59 4 2
     60 3
     61 5 3 1
     62 2 4 6
     63 5
     64 7 5 9 1 3
     65 2 4 6 10 8
     66 ```
     67 
     68 Output
     69 
     70 ```
     71 0
     72 2
     73 3
     74 ```
     75 
     76 Note
     77 
     78 In the first example, the array $a$ is already lexicographically smaller than array $b$, so no operations are required.
     79 
     80 In the second example, we can swap $5$ and $3$ and then swap $2$ and $4$, which results in $[3, 5, 1]$ and $[4, 2, 6]$. Another correct way is to swap $3$ and $1$ and then swap $5$ and $1$, which results in $[1, 5, 3]$ and $[2, 4, 6]$. Yet another correct way is to swap $4$ and $6$ and then swap $2$ and $6$, which results in $[5, 3, 1]$ and $[6, 2, 4]$.