In this post, we are going to solve Network Construction DSA Problem from Standard Chartered, On-Campus Questions. Let’s have a look at the problem statement first and then try to solve the problem.
Network Construction DSA Problem Statement
The developers of Hackerland want to construct a network of servers across the country to scale their applications. The country of Hackerland can be represented as a large coordinate grid and the developers have installed n servers across the country. The
server is located at coordinate
.
The cost of connecting any two servers indexed
and
is
where
represents the absolute value of an integer a.
Given the arrays
and
of
integers each, find the minimum cost of constructing the network such that every server is reachable by every other server via some direct or indirect connections.
The first line contains an integer
denoting number of servers.
The second line contains
space separated integers where
integer denotes
, where
.
The third line contains
space separated integers where
integer denotes
, where
.
Output the minimum possible cost to construct the network such that every server is reachable from every other server
3 2 4 8 6 10 9
3
DSA Problem Solution in C++:
#include <bits/stdc++.h>
using namespace std;
vector<int>par,sz;
void make(int n){
for(int i=0;i<n;i++){
par[i]=i;
sz[i]=1;
}
}
int find(int x){
if(par[x]==x)return x;
return par[x]=find(par[x]);
}
void Union(int x,int y){
x=find(x);
y=find(y);
if(x!=y){
swap(x,y);
par[y]=par[x];
sz[x]+=sz[y];
}
}
int main() {
int n;cin>>n;
vector<pair<int,int>>x,y;
for(int i=0;i<n;i++){
int a;cin>>a;
x.push_back({a,i});
}
for(int i=0;i<n;i++){
int b;cin>>b;
y.push_back({b,i});
}
sort(x.begin(),x.end());
sort(y.begin(),y.end());
vector<pair<int,pair<int,int>>>graph;
for(int i=0;i<n-1;i++){
graph.push_back({abs(x[i].first-x[i+1].first),{x[i].second,x[i+1].second}});
graph.push_back({abs(y[i].first-y[i+1].first),{y[i].second,y[i+1].second}});
}
sort(graph.begin(),graph.end());
par.resize(n);
sz.resize(n,0);
make(n);
long long cost=0;
for(auto it:graph){
int w=it.first;
int u=it.second.first;
int v=it.second.second;
if(find(u)!=find(v)){
Union(u,v);
cost+=w;
}
}
cout<<cost;
return 0;
}