h_sh
September 27, 2020, 7:00pm
1
Feels that tough and ended the test after solving 1 question. but wanna interested in knowing some better and tricky solutions so please share your idea and solution as it’s contest over so we can discuss.
For 4th - put max number at Bth position
for 3rd - Lemma . so direct equation you just need basic calculation but that is important.
PLease share others
1 Like
mohan14
September 27, 2020, 7:05pm
2
yea , anyone plz share how to do 3rd ,5th and 6th
h_sh
September 27, 2020, 7:06pm
3
did you solve 1 st , 2nd and 4th ? If yes then please share approach.
1 Like
for 2nd first find max depth of the tree
then upto min(depth+1,k) calculate no of nodes say n1.
ans = 2^(n1)
4 Likes
Looks like i overkilled it, i used dsu with binary lifting and answer was 2^components
8 Likes
Want to confirm idea on 6th, anyone?
Can someone please tell me where my code fails for FIRST question.It gave me a correct answer verdict for test.But on submitting it gave a wrong answer.
#include <bits/stdc++.h>
void bfs(vector<int> &A,int u,vector<vector<pair<int,int>>> &graph,vector<int> &ans,vector<int> &path,vector<int> &par,bool vis[])
{
ans[u]=A[u-1];
queue<int> s;
vis[u]=1;
path[u]=0;
s.push(u);
while(!s.empty())
{
int x=s.front();
ans[u]=min(ans[u],A[x-1]+2*path[x]);
s.pop();
for(pair<int,int> p:graph[x])
{
par[p.first]=x;
if(!vis[p.first])
{
path[p.first]=path[x]+p.second;
vis[p.first]=1;
s.push(p.first);
}
}
}
}
vector<int> Solution::solve(vector<int> &A, vector<vector<int>> &B) {
vector<vector<pair<int,int>>> graph(A.size()+1,vector<pair<int,int>>());
vector<int> ans(A.size()+1);
vector<int> path(A.size()+1);
vector<int> par(A.size()+1);
bool vis[A.size()+1];
vector<int> res(A.size());
for(vector<int> v:B)
{
graph[v[0]].push_back(make_pair(v[1],v[2]));
graph[v[1]].push_back(make_pair(v[0],v[2]));
}
for(int i=1;i<=A.size();i++)
{
bfs(A,i,graph,ans,path,par,vis);
memset(vis,0,A.size()+1);
par.clear();
path.clear();
}
for(int i=1;i<=A.size();i++)
{
res[i-1]=ans[i];
}
return res;
}
Anyone solved graph problem?
I tried it using dfs but didn’t worked!!
working with the cost for each edge created problems to me.Anyone done that question?
I did the exact same thing but on submitting it gave WA. Don’t know which case I am missing.
Hello, can anybody tell the expected rank at “x” number of problems solved ?
Thanks.
Does InterviewBit ever releases the result except the top 20 ?
Can you share your approach for 1,3,5,6 question @rohit_goyal
What was the idea of 5th ques ?
1st one:
A[u] = min(A[u], w*2 + A[v]);
A[v] = min(A[v], w*2 + A[u]);
repeat this for all edges until there are no more changes made to A
btme
September 28, 2020, 3:44pm
17
use multiple source djakstra
1 Like
Was the graph question so easy that almost everyone solved it? I am feeling dumb😣