A minimum sorting

Practice

4.3 (3 votes)

Dynamic programming and bit masking

Bitmask

Dynamic programming

Algorithms

Problem

70% Success 339 Attempts 50 Points 2s Time Limit 256MB Memory 1024 KB Max Code

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. 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

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 1 and B 2 and swap A 2 and B 1, 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 1 and B 2 and swap A 2 and B 1, 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.

Code Editor

You need to be logged in to access the code editor

Please wait while we load the editor

Submissions

Please login to view your submissions

You need to be logged in to access the code editor

Please wait while we load the editor