SortTwoArrays | Topcoder Archive

Problem Statement

You are given the int N and two arrays A and B, containing N elements each.

Your task is to transform the two arrays into a state in which both arrays are sorted. (The elements of A must be in non-descending order, and the elements of B must also be in non-descending order.)

You can only modify the arrays in one way: by swapping an element of A with an element of B.

For the two given arrays, determine whether it's possible to reach the goal by performing at most 3*N swaps. If a solution exists, find any one valid sequence of at most 3*N swaps.

Suppose that you found a sequence of K swaps, the i-th of which (for i=0..K-1) swaps the element number x[i] in A with the element number y[i] in B. Then, return the following int[]: { x[0], y[0], x[1], y[1], ..., x[K-1], y[K-1] }.

If there is no solution, return {-1}. That is, the return value is an array with a single element, and that element has the value -1.

Definition

Class:: SortTwoArrays
Method:: twoSorts
Parameters:: int, int[], int[]
Returns:: int[]
Method signature:: int[] twoSorts(int N, int[] A, int[] B)
(be sure your method is public)

Constraints

N will be between 1 and 999, inclusive.
A and B will have N elements each.
Each element of A and B will be between 0 and 999, inclusive.

Examples

```
3
```
```
{10, 20, 30}
```
```
{10, 20, 30}
```
```
Returns: {0, 0 }
```
Both arrays are already sorted, so we don't have to do any swaps at all. The example output does perform one swap: it swaps A[0] with B[0]. This illustrates that you are not required to minimize the number of swaps made.
```
5
```
```
{10, 11, 12, 22, 14}
```
```
{20, 21, 13, 23, 24}
```
```
Returns: {3, 2 }
```
Here we can make both arrays sorted by a single swap: swapping A[3] with B[2].
```
5
```
```
{10, 50, 60, 30, 80}
```
```
{20, 70, 99, 90, 40}
```
```
Returns: {1, 2, 3, 1, 1, 4 }
```
The example output describes a solution in three swaps: Swap A[1] with B[2]. Swap A[3] with B[1]. Swap A[1] with B[4]. The arrays change as follows: A B original {10, 50, 60, 30, 80} {20, 70, 99, 90, 40} after swap 1 {10, 99, 60, 30, 80} {20, 70, 50, 90, 40} after swap 2 {10, 99, 60, 70, 80} {20, 30, 50, 90, 40} after swap 3 {10, 40, 60, 70, 80} {20, 30, 50, 90, 99}
```
4
```
```
{1, 2, 90, 2}
```
```
{60, 70, 80, 2}
```
```
Returns: {2, 3 }
```
Note that some of the values in A and B may be equal. The example solution performs a single swap that turns A into the non-decreasing sequence {1, 2, 2, 2}.

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.