SortTwoArrays
SRM 835 · 2022-08-15 · by misof
Problem Statement
You are given the
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
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.
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.
5
{10, 11, 12, 14, 13}
{20, 24, 22, 23, 21}
Returns: {4, 1, 0, 3, 0, 4, 3, 2, 0, 3, 2, 0, 0, 2, 0, 2, 1, 1, 0, 0, 0, 1 }
According to the example output, we first swap A[3] with A[4] and then we swap B[4] with B[1].
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, 11, 12, 22, 14}
{20, 21, 23, 13, 24}
Returns: {4, 4, 0, 2, 0, 4, 3, 3, 3, 1, 2, 0, 0, 2, 1, 1, 0, 0, 0, 1 }
We swap A[3] with B[3] and then we swap B[2] and B[3]. There are many other valid solutions. Remember that as N=5, your sequence may consist of at most 5+3 = 8 swaps.
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}.
Submissions are judged against all 254 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class SortTwoArrays with a public method vector<int> twoSorts(int N, vector<int> A, vector<int> B) · 254 test cases · 2 s / 256 MB per case