Codeforces 441D - Valera and Swaps

Problem Statement:
441D - Valera and Swaps

Solution:
This problem is somewhat tedious in a sense that we need accuracy in swapping indexes and content of arrays.

The idea to solve this problem is from the (might be routine, but not so obvious on first try) observation that the minimum number of swaps required to place every element to its correct position is equal to the total number of elements in the "misplaced chain" minus one. What I mean by the misplaced chain is: Let a[i] be the elements in the sequence, and p[i] be the index of element i in array a[i]. If we start from position cur = i, and trace down all elements cur = p[cur], we will get a chain of misplaced elements. There will be several disjoint chains, and hence we can total up the total minimum number of swaps necessary to restore each element in each chain to its correct position, call this sum S. We can compare S and m, which leads us to three cases:

1. S is equal to m, then we don't have to do any more swaps.
2. S is bigger than m, then we need to break down the chain one element at a time so as to reduce S to m. This can be done by iterating through the chains, starting from one with smallest index, and correspondingly perform swapping of elements in the current chain so as to reduce S.
3. S is smaller than m, then we need to merge several chains together, two chains at a time. Notice that each time we merge two chain, S will increase by one.

Based on above strategy, solving the problem is a matter of accuracy and perseverance.

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

int a[3003];
int p[3003];
int ff[3003];
int pos[3003];
int vis[3003];
int n,m;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
        p[a[i]] = i;
    }
    scanf("%d",&m);
    int col = 0;
    int sum = 0;
    for(int i=1;i<=n;++i){
        if(ff[i] == 0){
            ++col;
            int cnt = 0;
            int cur = i;
            int root = cur;
            while(1) {
                ++cnt;
                ff[cur] = col;
                cur = p[cur];
                if(cur == root) break;
            }
            pos[col] = i;
            sum += (cnt-1);
        }
    }
    if(sum == m) {
        printf("0\n");
    } else if(sum > m) {
        //break down ff
        int k = sum - m;
        printf("%d\n",k);
        bool flag = false;
        for(int i=1;i<=n;++i){
            while(i != p[i]){
                int cur = p[i];
                int root = i;
                int smallest = 3005;
                while(cur != root) {
                    if(smallest > cur){
                        smallest = cur;
                    }
                    cur = p[cur];
                }
                int x,y,u,v;
                x = i;
                y = smallest;
                u = a[x];
                v = a[y];
                p[u] = y;
                p[v] = x;
                a[x] = v;
                a[y] = u;
                if(flag)printf(" ");
                printf("%d %d",x,y);
                --k;
                if(!flag) flag = true;
                if(k==0)break;

            }
            if(k==0)break;
        }
        printf("\n");
    } else {
        //merge ff
        int k = m-sum;
        printf("%d\n",k);
        bool flag = false;
        vis[1] = 1;
        for(int i=1;i<=n;++i){
            if(vis[ff[i]])continue;
            vis[ff[i]] = 1;
            if(flag)printf(" ");
            printf("1 %d", pos[ff[i]]);
            if(!flag)flag=true;
            --k;
            if(k==0)break;
        }
        printf("\n");
    }
    return 0;
}