Swap

christopherboo66

You have two arrays A and B, each contains numbers 1, 2, … , N, though not necessarily in this order.

In each operation, you can swap any two numbers in A.

Your task is to determine the least number of operations needed to transform A to B.

Input

  • The first line of the input contains an integer N, representing the size of arrays A and B.
  • The second line contains the elements of the array A, where consecutive elements are separated by a single space.
  • The third line contains the elements of the array B, where consecutive elements are separated by a single space.

Output

Output the minimum number of operations needed to transform A to B.

Constraints

  • Time Limit: 1s
  • Memory Limit: 64MB
  • 1 ≤ N ≤ 1,000,000

Sample Input

4
1 4 2 3
4 3 1 2

Sample Output

3

The 3 swap operations to transform [1,4,2,3] into [4,3,1,2] are:

Swap 1, 4
Swap 2, 3
Swap 1, 3

Problem Source : MCO 2014

Solution :

#include <iostream>

using namespace std;

void s(int &a, int &b){
    a = a + b;
    b = a - b;
    a = a - b;
}

int main(){

    int N;
    cin >> N;

    int A[N+1];
    for (int i=1; i<=N; i++){
        cin >> A[i];
    }

    int X[N+1];
    for (int i=1; i<=N; i++){
        cin >> X[A[i]];
    }

    int Y[N+1];
    for (int i=1; i<=N; i++){
        Y[X[i]] = i;
    }

    int cnt = 0;
    for (int i=1; i<=N; i++){
        if (X[i] != i){
            cnt++;

            s(X[i], X[Y[i]]);
            s(Y[X[i]], Y[X[Y[i]]]);
        }
    }

    cout << cnt;

    return 0;
}

The problem statement is pretty straightforward, but the solution was harder than I thought, since the time efficiency of a brute-force solution is O(n^2).

My approach is to rearrange sequence A to an ascending order, and the positions of elements in sequence B should also follow their responding element in sequence A. For example, instead of

1 4 2 3
4 3 1 2

we rearrange it to

1 2 3 4
4 1 2 3

In my solution, the second sequence is stored in X (line 21 ~ 24). With this, we can compare sequence X only by index :

for (int i=1; i<=N; i++){
    if (X[i] != i){
        // do something
    }
}

When we found out that the element in X is not same with its responding index, we should find for the right element to swap with it. The problem is, where and how do we find the right element to swap? For example in the first case, we know that 4 should be changed to 1, but how do we find the position of 1?

Of course, you can scan through the entire sequence, but that gives you a time efficiency of O(n^2). The better idea is to record the index of every element in sequence X. For example in sequence

4 1 2 3

We should record the index of 1, which is 2 (I prefer counting from 1 instead of 0 in this problem). Similarly, 2 will be record as 3, and go on we have a sequence

2 3 4 1

In my solution, I named this sequence as Y. With the aid of this sequence, when we found an element in sequence X that differs from its index, we do as follow :

if (X[i] != i){
    swap(X[i] , X[Y[i]]);
}

After we swapped the two elements, there would also be a minor change in sequence Y, since it recorded the indexes of elements in sequence X. Since the position of X[i] and X[Y[i]] are swapped, their indexes are also swapped.

swap(Y[X[i]], Y[X[Y[i]]]);

Finally, we have all the tools to solve this problem! Good luck problem solving!

Swap

Leave a comment