# CodeAgon 2020

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.

1 Like

yea , anyone plz share how to do 3rd ,5th and 6th

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

use multiple source djakstra

1 Like

Was the graph question so easy that almost everyone solved it? I am feeling dumb😣