Beautiful Permutation - Editorial

About the Problem

Setter(s) Jatin Garg
Tester(s) Vichitr Gandas, Mayank Pugalia, Aswin Ashok
Difficulty Medium
Topics Graph, Observations, Greedy, MST, Boruvka’s Algorithm
Practice Link
Contest Link

Solution Idea

Permutation is nothing but set of disjoint cycles.

In beautiful permutation there is only one single cycle of size n .

Observations

  • Swapping any two indexes either merge two cycles or split some cycle.
  • Obviously splitting any cycle will always be non-optimal, so we will consider only merging of some cycles.
  • So we some K cycles, we have to merge them into one using minimum cost, this problem is almost same as finding MST , by assuming cycles as nodes.

There will be O(n^2) edges so we can not use any standard algorithm to find MST.

Now there are two methods to find MST.

Method 1: Greedy Algorithm

  • Assume indexes (i,j,k,l) were involved in swap operation, and assume C_i \leq C_j \leq C_k \leq C_l .
  • Now there will not be any set of edges in MST , which includes both (C_i,C_k) and (C_j,C_l) . Instead of these two edges, we can select (C_i,C_j) and (C_k,C_l) .
  • So just sort all the cost_i 's and add edge between two consecutive indexes in sorted order if they are not in same cycle.
  • Now just build the MST with these edges.

Complexity Analysis:

  • Time Complexity: O(n \log{n})
  • Space Complexity: O(n)

Method 2: Boruvka’s Algorithm

  • This method involves a non-standard algorithm Boruvka’s Algorithm . We can solve much more complex cost function using this algorithm.
  • In starting suppose there are n components, then in every iteration we find best outgoing edge for every component using some data structure such as C++ Set , and these edges into the MST, after every iteration Number of components will be halved, hence there will be O(\log{n}) iterations, every iteration costs O(n \log{n}) ,so Time Complexity would be O(n \log^2{n}) .

Complexity Analysis:

  • Time Complexity: O(n \log^2{n})
  • Space Complexity: O(n \log{n})

Codes

Setter's Code
// Jai Shree Ram  
  
#include<bits/stdc++.h>
using namespace std;

#define rep(i,a,n)     for(int i=a;i<n;i++)
//#define int            long long
#define x              first
#define y              second
#define pii            pair<int,int>


template<typename T1,typename T2>istream& operator>>(istream& in,pair<T1,T2> &a){in>>a.x>>a.y;return in;}
template<typename T1,typename T2>ostream& operator<<(ostream& out,pair<T1,T2> a){out<<a.x<<" "<<a.y;return out;}
template<typename T,typename T1>T maxs(T &a,T1 b){if(b>a)a=b;return a;}
template<typename T,typename T1>T mins(T &a,T1 b){if(b<a)a=b;return a;}

const int maxn = 2e6 + 5;
int p[maxn];
int sz[maxn];
int cnt = 0;
void clear(int n){
    rep(i,0,n+1)p[i]=i,sz[i]=1;
}
int root(int x){
   while(x!=p[x]){
       p[x]=p[p[x]];
       x=p[x];
   }
   return x;  
}
void merge(int x,int y){
    int p1=root(x);
    int p2=root(y);
    if(p1==p2)return;
    cnt--;
    if(sz[p1]>=sz[p2]){
        p[p2]=p1;
        sz[p1]+=sz[p2];
    }
    else{
        p[p1]=p2;
        sz[p2]+=sz[p1];
    }
}

int solve(){
 
	int n; cin >> n;

	vector<int>p(n+1),cost(n+1);

	rep(i,1,n+1){
	
		cin >> p[i];
	}

	rep(i,1,n+1){

		cin >> cost[i];
	}


	auto greedy = [&]() -> int{

		clear(n);
		cnt = n;
		for(int i = 1; i <= n; i++){
			merge(i,p[i]);
		}

		vector<pii>sorted_cost;

		for(int i = 1; i <= n; i++){
			sorted_cost.push_back({cost[i],i});
		}

		sort(sorted_cost.begin(),sorted_cost.end());

		vector<pair<int,pii>>edges;

		for(int i = 1; i < n; i++){
			int u = root(sorted_cost[i].y);
			int v = root(sorted_cost[i-1].y);
			int w = abs(sorted_cost[i].x - sorted_cost[i-1].x);
			if(u != v){
				edges.push_back({w,{u,v}});
			}
		}

		sort(edges.begin(),edges.end());

		int ans = 0;
		for(auto i:edges){
			if(root(i.y.x) != root(i.y.y)){
				merge(i.y.x,i.y.y);
				ans += i.x;
			}	
		}
		return ans;
	};
	cout << greedy() << endl;
 return 0;
}



signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #ifdef SIEVE
    sieve();
    #endif
    #ifdef NCR
    init();
    #endif
    int t;cin>>t;
    while(t--)solve();
    return 0;
}
 
Tester's Code 1
/***************************************************

@author: vichitr
Compiled On: 27 Mar 2021

*****************************************************/
#include<bits/stdc++.h>
#define MAX 9223372036854775807
#define endl "\n"
#define ll long long
#define int long long
// #define double long double
#define pb push_back
#define pf pop_front
#define mp make_pair
#define ip pair<int, int>
#define F first
#define S second

#define loop(i,n) for(int i=0;i<n;i++)
#define loops(i,s,n) for(int i=s;i<=n;i++)
#define fast ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL)
using namespace std;

// #include <ext/pb_ds/assoc_container.hpp> // Common file
// #include <ext/pb_ds/tree_policy.hpp>     // Including tree_order_statistics_node_updat
// using namespace __gnu_pbds;
// typedef tree<ip, null_type, less_equal<ip>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

// order_of_key (k) : Number of items strictly smaller than k .
// find_by_order(k) : K-th element in a set (counting from zero).

const ll MOD = 1e9+7;
const ll SZ = 107;
const ll N = 1e6+7;
const ll M = 1e4+7;

ll pwr(ll x, ll y)
{
    ll r = 1LL;
    while(y)
    {
        if(y&1)
            r = (r * x) % MOD;
        y >>= 1;
        x = (x * x) % MOD;
    }
    return r;
}

int inv(int x)
{
    return pwr(x, MOD-2ll);
}

int parent[N], siz[N];

int find_set(int v) {
    if (v == parent[v])
        return v;
    return parent[v] = find_set(parent[v]);
}

void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        if (siz[a] < siz[b])
            swap(a, b);
        parent[b] = a;
        siz[a] += siz[b];
    }
}

void solve(){
    int n; cin>>n;
    int p[n+1], c[n+1];
    loops(i, 1, n) cin>>p[i];
    loops(i, 1, n) cin>>c[i];

    for(int i=0;i<=n;i++){
        parent[i] = i;
        siz[i] = 1;
    }

    vector<pair<int, int>> v;

    loops(i, 1, n){
        union_sets(i, p[i]);
        v.pb({c[i], p[i]});
    }
    sort(v.begin(), v.end());
    
    vector<vector<int>> e;
    for(int i=1;i<n;i++){
        int x = v[i-1].second;
        int y = v[i].second;
        int w = abs(v[i].first - v[i-1].first);
        x = find_set(x);
        y = find_set(y);
        if(x != y)
            e.pb({w, x, y});
    }

    sort(e.begin(), e.end());
    int ans = 0;
    for(int i=0;i<e.size();i++){
        int w = e[i][0];
        int x = e[i][1];
        int y = e[i][2];
        if(find_set(x) != find_set(y)){
            ans += w;
            union_sets(x, y);
        }
    }
    cout << ans << '\n';
}

signed main()
{
    // fast;
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    
    
    int t=1;
    cin >> t;
    assert(t <= 1e5);
    for(int i=1;i<=t;i++)
    {
        // cout<<"Case #"<<i<<": ";
        solve();
        
    }
    return 0;
}

Tester's Code 2
#include <bits/stdc++.h> 
using namespace std;
vector<int> Arr;
int root(int i)
{
    while(Arr[ i ] != i)           
    {
        i = Arr[ i ];
    }
    return i;
}
void un(int A ,int B)
{
    int root_A = root(A);       
    int root_B = root(B);  
    Arr[ root_A ] = root_B ;      
}
bool find(int A,int B)
{
    if( root(A)==root(B) ) 
        return true;
    else
        return false;
}
void solve()
{
    int n;
    cin>>n;
    vector<int> p(n+1);
    vector<int> cost(n+1);
    vector<pair<int,int>> cp;
    Arr.clear();
    Arr.resize(n+1);
    for(int i=0;i<=n;++i)
        Arr[i]=i;
    for(int i=1;i<=n;++i)
    {
        cin>>p[i];
    }
    for(int i=1;i<=n;++i)
    {
        if(!find(i,p[i]))
            un(i,p[i]);
    }
    for(int i=1;i<=n;++i)
        cin>>cost[i]; 
    for(int i=1;i<=n;++i)
        cp.push_back({cost[i],p[i]});
    sort(cp.begin(),cp.end());
    vector<pair<int, pair<int,int> > > edges;
    for(int i=1;i<cp.size();++i)
    {
        int cost = abs(cp[i].first - cp[i-1].first);
        int u = cp[i].second;
        int v = cp[i-1].second;
        edges.push_back({cost,{u,v}});
    }
    sort(edges.begin(),edges.end());
    long long ans = 0;
    for(int i=0;i<edges.size();++i)
    {
        int cost = edges[i].first;
        int u = edges[i].second.first;
        int v = edges[i].second.second;
        if(!find(u,v))
        {
            ans+=cost;
            un(u,v);
        }
    }
    cout<<ans<<endl;
    
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        solve();
    }
}

If you have used any other approach, share your approach in comments!
If you have any doubts, ask them in comments!

3 Likes