Header Ad

HackerEarth To buy or not to buy problem solution

In this HackerEarth To buy or not to buy problem solution Suraj a software engineer from Mumbai just got placed in a software company in New Delhi. As, he have to relocate from Mumbai to Delhi, he decided to buy a house. Yeah price of houses have decreased after Narendra Modi became PM of India. He decided to buy a house in a locality which has burger points at each corner. As the streets are only one way there is a heavy traffic jam and it take time to Suraj to reach burger point. Modi just declared that he will convert some streets connecting these burger points to two way roads. Some conversion cost is associated with each street. It will cost lot of money to convert all streets to two way streets so Modi wanted these conversion in such a way that total cost of conversion is minimized keeping in mind that all burger points are connected with two way roads. Suraj after coming to know about this idea decided to buy a house in a two way street. But not all streets will be two way. So, he ask you to tell him if he should buy house in a particular street or not. As there can be more than one conversion plan, help Suraj to decide if he should buy house in that street or not. You will be given m queries by Suraj. Your task is to tell for how many queries will the answer be yes. Return ans in the form of a/b where a is the no. of queries for which ans is yes and b is total number of queries. (gcd(a,b) should be 1).

There will be n burger points and k streets joining them.


HackerEarth To buy or not to buy problem solution


HackerEarth To buy or not to buy problem solution.

#include<bits/stdc++.h>
using namespace std;
struct node
{
int dest;
int weight;
};
struct edge
{
int src;
int dest;
int weight;
};
vector<node> adj[1000005];
bool visited[1000005];
int ter;
map<pair<int,int>, int> mapped;
int gcd(int a, int b)
{
if(b)
return gcd(b,a%b);
return a;
}
void dfs(int n)
{
visited[n]=true;
for(int i=0;i<adj[n].size();++i)
{
if(!visited[adj[n][i].dest])
dfs(adj[n][i].dest);
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
mapped.clear();
int n,m,s,te,w;
scanf("%d %d",&n,&m);
vector<edge> v;
node e;
edge e1;
for(int i=0;i<m;++i)
{
scanf("%d %d %d",&s,&te,&w);
e1.src=s;
e1.dest=te;
e1.weight=w;
v.push_back(e1);
mapped.insert(make_pair(make_pair(s,te),w));
mapped.insert(make_pair(make_pair(te,s),w));
}
int q,ans=0,que;
scanf("%d",&q);
que=q;
while(q--)
{
memset(visited,false,sizeof(visited));
for(int i=0;i<1000;++i)
adj[i].clear();
int s,w;
scanf("%d %d",&s,&ter);
w=mapped[make_pair(s,ter)];
node n;
for(int i=0;i<v.size();++i)
{
if(v[i].weight<w)
{
n.dest=v[i].dest;
n.weight=v[i].weight;
adj[v[i].src].push_back(n);
n.dest=v[i].src;
adj[v[i].dest].push_back(n);
}
}
dfs(s);
if(!visited[ter])
ans++;
}
int a=gcd(ans,que);
printf("%d/%d\n",ans/a,que/a);
}
return 0;
}

Second solution

#include<bits/stdc++.h>
using namespace std;
#define vi vector < int >
#define pb push_back
#define mp make_pair
#define ll long long
#define llu unsigned long long
#define MOD 1000000007
#define INF 2000000000
#define dbg(x) { cout<< #x << ": " << (x) << endl; }
#define all(x) x.begin(),x.end()
vector < vi > adj,cost;
int a[1001][1001];
int vis[1001];
void dfs(int node,int c)
{
vis[node] = 1;
int i;
for(i=0;i<adj[node].size();i++)
{
int nxt = adj[node][i];
if(!vis[nxt] && cost[node][i] < c)
dfs(nxt,c);
}
}
int main()
{
int t,n,m,i,j;
scanf("%d",&t);
assert(1<=t && t<=15);
while(t--)
{
scanf("%d%d",&n,&m);
int M = m;
assert(1<=n && n<=1000);
assert(m <= min(1001,(n*(n-1)/2)-n) + n);
adj.resize(n+1);
cost.resize(n+1);
for(i=0;i<=n;i++)
{
adj[i].clear();
cost[i].clear();
for(j=0;j<=n;j++)
a[i][j] = 0;
}
while(m--)
{
int u,v,c;
scanf("%d%d%d",&u,&v,&c);
assert(1<=u && u<=n);
assert(1<=v && v<=n);
assert(1<=c && c<=100);
adj[u].pb(v);
cost[u].pb(c);
adj[v].pb(u);
cost[v].pb(c);
a[u][v] = a[v][u] = c;
}
int q;
scanf("%d",&q);
assert(1<=q && q<=M);
int num = 0 , den = q;
while(q--)
{
int u,v;
scanf("%d%d",&u,&v);
assert(1<=u && u<=n);
assert(1<=v && v<=n);
assert(a[u][v]);
for(i=1;i<=n;i++)
vis[i] = 0;
dfs(u,a[u][v]);
if(!vis[v])
num++;
}
int g = __gcd(num,den);
num/=g;
den/=g;
printf("%d/%d\n",num,den);
}
return 0;
}

Post a Comment

0 Comments