A minimum sorting

★★★★★

4.3

3 votes

Dynamic Programming and Bit Masking, Bitmask, Dynamic Programming, Algorithms

Details

Problem

You are given two arrays $A$ and $B$ of size $N$ . Your task is to sort array A (non-decreasing) by using the following operation for the minimum number of times.

Operation steps are:

Select any index $i$ such that $1\le i<N$ .
Swap $A_i$ and $B_{i+1}$ .
Swap $A_{i+1}$ and $B_i$ .

If there is a way to sort array $A$ using the above operation, then find the minimum number of operations that must be performed. If it is impossible to sort the array, then print -1.

Input format

The first line contains an integer $T$ denoting the number of test cases. For each test case:
The first line of each test case contains an integer $N$ denoting the number of elements in arrays $A$ and $B$ .
The second line of each test case contains $N$ space-separated integers of array $A$ .
The third line of each test case contains $N$ space-separated integers of array $B$ .

Output format

For each test case, print a single line indicating the minimum number of operations if sorting can be done. If it is not possible to sort the array, print -1.

Constraints

$1 \leq T \leq 5$

$1 \leq N \leq 16$

$1 \leq A_i , B_i \leq 100$

Sample Input

Sample Output

0
-1
1

Time Limit: 2

Memory Limit: 256

Source Limit:

Explanation

First test case:
The array A is already sorted, so we don't need to perform any operation.

Second test case:
The array A is initially not sorted, A={8,7} and B={7,8}, we need to perform operation. We have no other choice than choosing index as 1, according to operation we need to swap A₁ and B₂ and swap A₂ and B₁, after performing array A={8,7} and B={7,8} remains the same and we have no other options, so it is impossible to sort the array.

Third test case:
A={2,3,2} and B={2,1,2} and let us choose i=1, according to operation we need to swap A₁ and B₂ and swap A₂ and B₁, after performing array A={1,2,2} and B={3,2,2} and now note that array A is sorted. Number of operations in this case are 1.

Contributers:

SHUBHAM KHANDELWAL

Arpa PoorAkhavan