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!