Chefina and Swaps | CHFNSWPS | CodeChef

Chefina has two sequences A1,A2,…,AN$A_1,A_2,\dots ,A_N$ and B1,B2,…,BN$B_1,B_2,\dots ,B_N$. She views two sequences with length N$N$ as identical if, after they are sorted in non-decreasing order, the i$i$-th element of one sequence is equal to the i$i$-th element of the other sequence for each i$i$ (1≤i≤N$1\le i\le N$).

To impress Chefina, Chef wants to make the sequences identical. He may perform the following operation zero or more times: choose two integers i$i$ and j$j$ (1≤i,j≤N)$(1\le i,j\le N)$ and swap Ai$A_i$ with Bj$B_j$. The cost of each such operation is min(Ai,Bj)$\mathrm{m}\mathrm{i}\mathrm{n}(A_i,B_j)$.

You have to find the minimum total cost with which Chef can make the two sequences identical.

Input

• The first line of the input contains a single integer T$T$ denoting the number of test cases. The description of T$T$ test cases follows.
• The first line of each test case contains a single integer N$N$.
• The second line contains N$N$ space-separated integers A1,A2,…,AN$A_1,A_2,\dots ,A_N$.
• The third line contains N$N$ space-separated integers B1,B2,…,BN$B_1,B_2,\dots ,B_N$.

Output

For each test case, print a single line containing one integer ― the minimum cost, or 

−1$-1$ if no valid sequence of operations exists.

Constraints

• 1≤T≤2,000$1\le T\le 2,000$
• 1≤N≤2⋅105$1\le N\le 2\cdot {10}^5$
• 1≤Ai,Bi≤109$1\le A_i,B_i\le {10}^9$ for each valid i$i$
• the sum of N$N$ over all test cases does not exceed 2⋅106$2\cdot {10}^6$

Subtasks

Subtask #1 (15 points):

• T≤20$T\le 20$
• N≤20$N\le 20$

Subtask #2 (85 points): original constraints

Example Input

3
1
1
2
2
1 2
2 1
2
1 1
2 2

Example Output

-1
0
1

Explanation

Example case 1: There is no way to make the sequences identical, so the answer is −1$-1$.

Example case 2: The sequence is identical initially, so the answer is 0$0$.

Example case 3: We can swap A1$A_1$ with B2$B_2$, which makes the two sequences identical, so the answer is 1$1$.

Solution (Python 3)

def check(newA,mini,lmina):

    for i in newA:

        if i > mini:

            break

        lmina += 1

    return lmina

    

test = int(input())

for _ in range(test):

    n = int(input())

    cost = 0

    s= set()

    freq1 = {}

    imini = 2**31

    freq2 = {}

    arr1 = list(map(int, input().split()))

    arr2 = list(map(int, input().split()))

    toMoveA = []

    toMoveB = []

    p=0

    for each in arr1:

        p=p^each;

    for each in arr2:

        p=p^each

    if p==0:

        lenA=lenB=0

        for i in arr1:

            if (i in freq1):

                freq1[i] += 1

            else:

                freq1[i] = 1

                freq2[i] = 0

                s.add(i)

        for i in arr2:

            if (i in freq2):

                freq2[i] += 1

            else:

                freq2[i] = 1

                if i not in s:

                    freq1[i] = 0

                    s.add(i)

        for i in s:

            c1 = freq1[i]

            c2 = freq2[i]

            if(imini > i):

                imini = i

            if(c1 < c2):

                for j in range((c2 - c1) >> 1):

                    toMoveB.append(i)

                    lenB += 1

            elif(c2 < c1):

                for j in range((c1 - c2) >> 1):

                    toMoveA.append(i)

                    lenA += 1

        newA = sorted(toMoveA)

        newB = sorted(toMoveB)

        imini *= 2

        lmina = lminb = 0

        lmina = check(newA,imini,lmina)

        gmina = lenA-lmina

        lminb = check(newB,imini,lminb)

        gminb = lenB - lminb

        if(lmina <= gminb):

            for i in newA[:lmina]:

                cost += i

            for i in newB[:lminb]:

                cost += i

            cost += (imini * (gmina - lminb))

        else:

            for i in newA[:(gminb)]:

                cost += i

            for i in newB[:(gmina)]:

                cost += i

            i = gminb

            j = gmina

            for k in range(lminb - gmina):

                if(newA[i] < newB[j]):

                    cost += newA[i]

                    i += 1

                else:

                    cost += newB[j]

                    j += 1

        print(cost)

    else:

        print(-1)