In this post, we are going to solve Damaged Roads DSA Problem from MediaNet Online assessment. Let’s have a look at the problem statement first and then try to solve the problem.
Damaged Roads DSA Problem Statement
You are the Prime Minister of a country and once you went for a world tour.
After 5 years, when you returned to your country you were shocked to see the condition of the roads between the cities. So, you plan to repair them, but you cannot afford to spend a lot of money.
The country can be represented as a N*M grid, where Country[i,j] is a city.
The cost of repairing a repairing a road between [i,j] and [i+1,j] is A[i].
The cost of repairing a road between [i,j] and [i,j+1] is B[i].
Return the minimum cost of repairing roads such that all cities become a connected network.
As the cost can be large, return the cost modulo
.
First line contains 2 space separated values N , M.
Second line contains N-1 values corresponding to content of A.
Third line contains M-1 values corresponding to content of B.
Constraints
Return an integer representing the minimum possible cost.
4 4 1 1 1 1 1 2
16
4 4 1 2 3 4 5 6
39
Damaged Roads DSA Problem Solution in C++
#include <bits/stdc++.h>
using namespace std;
int main() {
int n,m;
cin>>n>>m;
int mod=1e9+7;
vector<int> a(n-1),b(m-1);
for(int i=0;i<n-1;i++) cin>>a[i];
for(int i=0;i<m-1;i++) cin>>b[i];
long long ans=0;
vector<pair<int,int>> v;
for(int i=0;i<n-1;i++) v.push_back({a[i],0});
for(int i=0;i<m-1;i++) v.push_back({b[i],1});
sort(v.begin(),v.end());
int r=0,c=0;
for(int i=0;i<v.size();i++){
if(v[i].second==0){
ans+=(m-c)*v[i].first;
r++;
}
else{
ans+=(n-r)*v[i].first;
c++;
}
}
ans=ans%mod;
cout<<ans;
return 0;
}