Naruto and One Shot (Graph ques.)

https://www.codechef.com/ENAU2020/problems/ECAUG207
can someone help here please…i am not able to understand the test cases…can anyone explain ?
Thank you in advance :slight_smile:

so see bro we are given a tree so lets say i consider the first test case:

5
1 2
1 3
2 4
3 5

so there is an edge between 1 & 2, 1 & 3 , 2& 4 , 3&5

5<-3<-1->2->4 this is how the graph should like . So lets say I don’t use the special operation before attacking any town , I have to face 5 warriors at a time .
Now if i use the special operation on node 1 then there will be no edge between 1 and 2 , and between 1 and 3 . So in this process I capture node 1 and then there will be two components of graph left i.e 5->3 and 2->4.
So if i attack at 2(because its being now disconnected) I have to face 2 warriors now.

Note : 1 is the optimum node now lets say what if i use special operation on node 2 then
1 and 2 will get disconnected and the graphs remaining are 5<-3<-1 & 2<-4.

So now if i attack at node 3 then i have to face 3 warriors at a time which is not optimum so I should have selected 1 which is like the mid point.

Try to figure out the 2nd test case .If u don’t understand I can help and also whenever u post doubts tag admin and problem setter he can help u with the editorial.:slight_smile:

1 Like

thank you sooooo much @kanisht09 for helping me :slight_smile: this tutorial is very very helpful for me :innocent:

u r welcome bro :smile:

@sandeep1103 please share the editorial , i m having difficulty in the implementation. would be a great help :slight_smile:

1 Like

I have but the code which i have is not mine i picked someone’s code and modify that code according to me and then try to understand the test cases. I had picked this code before your wonderful help :sweat_smile:

#include <bits/stdc++.h>
using namespace std;
int n;
int dfs(vector<vector>&a,vector &vis,int x,int &X,int &W){
int ans=0,num=1;
vis[x]=true;
for(int i:a[x]){
if(!vis[i]){
int tmp=dfs(a,vis,i,X,W);
num+=tmp;
ans=max(ans,tmp);
}
}
ans=max(ans,n-num);
if(ans<W)
X=x,W=ans;
else if(ans==W)
X=min(X,x);
return num;
}

int main(){
int t; cin>>t;
while(t–){
cin>>n;
vector<vector> a(n+1);
for(int i=1;i<n;i++){
int X,v;
cin>>X>>v;
a[X].push_back(v);
a[v].push_back(X);
}
vectorvis(n+1,false);
int X=INT_MAX,W=INT_MAX;
dfs(a,vis,1,X,W);
cout<<X<<" "<<W<<endl;
}
return 0;
}

Blockquote

Hey!! bro can you share your approach of Notebook Distribution ques. https://www.codechef.com/ENAU2020/problems/ECAUG205 i am having trouble to implement this.

Naruto and one shot

The editorial has been posted.

2 Likes

The question basically asks you to find the centroid of the tree. Centroid of the tree is a node whose subtree size does not exceed N/2 (N being the number of nodes). You can check out my submission here:
https://www.codechef.com/viewsolution/37349513

1 Like

You can simply binary Search over the answer. Here, have a look at my submission and let me know if you are not able to understand anything.
https://www.codechef.com/viewsolution/37345796

https://www.codechef.com/viewsolution/37372711
dp denotes subtree size . let me know if u have any issue.

2 Likes

well as far subtree is involved can u please suggest me some starter problems so it would be easy for me to solve this .Like using dfs i can calculate connected components ,length of each connected component and print the node which is a part of the component and where can i learn this. Please reply @ssrivastava990 ,@harsh0911

Bro there are many blogs over codeforces , just google it -
for questions -
https://codeforces.com/blog/entry/55274

2 Likes

wow its really nice thanks for ur help :smile:

1 Like

https://codeforces.com/blog/entry/16221
Great place to learn certain basic algorithms and also practise questions.

To practise, I recommend to apply filters on codeforces and then practise to increase your level, gradually moving on to more complex problems.
https://codeforces.com/problemset?order=BY_RATING_ASC&tags=graphs%2Ctrees%2Cdfs+and+similar

1 Like

googling skills matters :stuck_out_tongue_winking_eye:

2 Likes

I used binary search for this problem
Here is my solution : https://www.codechef.com/viewsolution/37366022

And if u want to learn how to apply binary search for problems like this do watch Coden code utube channel’s playlist on binary search.It really helped me a lot.

can you explain your logic ? i know how to use binary search but still i am able to think why we use this .

Encoding August 20 Problem Name-Notebook Distribution visit here i had the same problem like u :frowning: