Swaps (Codeforces 1573B)
Tags: Math, sortings

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.You can perform the following operation on those arrays:   choose one of the two arrays  pick an index $$$i$$$ from $$$1$$$ to $$$n-1$$$  swap the $$$i$$$-th and the $$$(i+1)$$$-th elements of the chosen array  Compute the minimum number of operations needed to make array $$$a$$$ lexicographically smaller than array $$$b$$$.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$$$.

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$).The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the length of the arrays.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$$$.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$$$.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output: For each test case, print one integer: the minimum number of operations needed to make array $$$a$$$ lexicographically smaller than array $$$b$$$.We can show that an answer always exists.

Note: In the first example, the array $$$a$$$ is already lexicographically smaller than array $$$b$$$, so no operations are required.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]$$$.

Sample Inputs:
3
2
3 1
4 2
3
5 3 1
2 4 6
5
7 5 9 1 3
2 4 6 10 8

Sample Outputs:
0
2
3

Solution (Python):
import sys
MOD = 1000000007

def main():
    t = int(input())
    for tt in range(t):
        n = int(input())
        a = list(map(int, input().split()))
        b = list(map(int, input().split()))
        j = 1
        index = {}
        for i in range(n):
            while j < b[i]:
                index[j] = i
                j += 2
        ans = sys.maxsize
        for i in range(n):
            ans = min(ans, i + index[a[i]])
        print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
def solve():
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    dic = {}
    for i in range(n):
        dic[a[i]] = i
    ans = n
    j = 0
    for i in range(1, n * 2, 2):
        while j < n and b[j] < i:
            j += 1
        ans = min(ans, dic[i] + j)
    print(ans)
t = int(input())
while t:
    solve()
    t -= 1

Solution (Python):
def solve():
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    j = 1
    index = {}
    for i in range(n):
        while j < b[i]:
            index[j] = i
            j += 2
    ans = float('inf')
    for i in range(n):
        ans = min(ans, i + index[a[i]])
    print(ans)
if __name__ == '__main__':
    t = int(input())
    for _ in range(t):
        solve()