ENCDEC09 - Editorial

PROBLEM LINK:

Practice
Contest

Author: Sunita Sen
Editorialist: Sunita Sen

DIFFICULTY:

MED-HARD

PREREQUISITES:

DSU

PROBLEM:

Given an array of pairs, we will have to rearrange elements such that each pair is together.

EXPLANATION:

Let us consider the size of the array as N. Then, there will N/2 number of pairs.
So we traverse pairs one by one. There could be two cases here:

  1. Both the elements form a pair:
    Then we need not do anything here.
  2. The elements are from different pairs:
    Let us consider that elements are two different pairs a and b. We can consider that there is an edge between them. So after connecting all the edges we will find several connected components. So we will need (SizeofComponent - 1) swaps for each component.

SOLUTIONS:

Cpp Solution
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<(n);i++)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define dfor(i,a,b) for(ll i=(a);i>=(b);i--)
#define mem(a, vis) memset(a, vis, sizeof(a))
#define ll long long
#define ull unsigned long long
#define MOD  1000000007
#define MAX  1e9
#define F    first
#define S    second


long find(long a, vector<long> &p, vector<long> &sz) {
    return p[a] == a ? a : p[a] = find(p[a], p, sz);
}
void connect(long a, long b, vector<long> &p, vector<long> &sz) {
    long pa = find(a, p, sz);
    long pb = find(b, p, sz);
    if (pa == pb) {
        return;
    }
    if (sz[pa] >= sz[pb]) {
        p[pb] = pa;
        sz[pa] += sz[pb];
    } else {
        p[pa] = pb;
        sz[pb] += sz[pa];
    }
}

long solve(vector<long>& row) {
    long n = row.size() / 2;
    long nn = row.size();
    vector<long> p(n), sz(n, 1);
    rep(i,n) 
        p[i] = i;
    rep(i,n) {
        long a = (nn - row[i * 2]) / 2;
        long b = (nn - row[(i * 2) + 1]) / 2;
        connect(a, b, p, sz);
    }
    long ans = 0;
    rep(i,n) {
        if (find(i, p, sz) == i) {
            ans += sz[i] - 1;
        }
    }
    
    return ans;
}

signed main(){
    long t = 1;
    cin>>t;
    while(t--){
        long n;
        cin>>n;
        vector<long> v(n);
        rep(i,n) {
            cin>>v[i];
        }

        long ans = solve(v);
        cout<<ans<<endl;
        
    }
}
2 Likes