PERCAPTA - Editorial

editorial
, , , , ,
55

Hi guys Try this video solution: [Per Capita Income]](Codechef June Cook-Off 2020 | |Per Capita Income || Steps and explaination || CODECHEF - YouTube)

56

even i also applied the same approach ,but getting TLE.I also tried implementing using scanf and printf for i/o but still getting TLE

57

Thanks

1 Like
58

Nice question.

60

Hi guys try this video solution :raised_hands::raised_hands:

61

Very week testcases, have a look at this

62

You should have add some testcases with these corner cases

63

I have used the same dfs approach, but getting wa verdict. Can someone please help. Thanks!!
https://www.codechef.com/viewsolution/34626836

Edit: that’s due to integer overflow :cry: changed to long long, got AC.

64

Can anyone Please explain how to calculate num/den not by dividing.
How this is working a[i]den>numb[i].

I am getting TLE on easy dfs
void dfs(int node,unordered_map<int,vector> g,map<int,bool>& mp){
// cout<<node<<endl;
vis[node]=true;
mp[node]=false;
res.insert(node);
for(auto child:g[node]){
if(!vis[child]){
dfs(child,g,mp);
}
}
}
int main() {
int testCase,n,m,x,y;
cin>>testCase;
while(testCase–){
cin>>n>>m;
int a[n+1],b[n+1];
float p[n+1];
float maxx=-1;
map<int,bool> mp;
unordered_map<int,vector> g;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++){
cin>>b[i];
p[i]=((a[i]*1.0)/(b[i]*1.0));
maxx=max(maxx,p[i]);
}
for(int i=1;i<=n;i++){
if(p[i]==maxx) mp[i]=true;
}
while(m–){
cin>>x>>y;
if(mp[x]==true&&mp[y]==true){
g[x].push_back(y);
g[y].push_back(x);
}
}
set ans;
for(auto r:mp){
if(r.second==false) continue;
// cout<<r.first<<endl;
dfs(r.first,g,mp);
if(res.size()>ans.size()) ans=res;
res.clear();vis.clear();
}
cout<<ans.size()<<endl;
for(auto c:ans) cout<<c<<’ ';
cout<<endl;
}
return 0;
}

https://www.codechef.com/viewsolution/34626399

65

Hello everybody! After reading the editorial, I wrote a code that uses DFS but it is showing time out for me. So, I decided to copy and Paste “Tester’s Code” (which also uses DFS), but it is showing runtime error in that too. What is going on?
https://www.codechef.com/viewsolution/34627355
Please look into this matter…

66

I ran it with C++ 17 it shows error but with C++14 it is working fine. Any ideas as to what can explain this?

67

Initially I was getting WA with DFS. Solution Link.

Then I modified that same code just by not selecting any edge to the non - desired provinces in the graph itself (i.e. I’m not even creating that edge in the Adjacency List) and it got AC. Solution Link.

Now I’m all the more curious about what is going wrong in the first solution.

Anyone please look in the codes and suggest strong cases where it’s going wrong.

@taran_1407 please help sir !!

69

@anon55283797 fast input output use kar le ,ye inki alag level ki bakchodi h ,mai buri tarah se frustrate ho gya iski wajah se

70

TL was somewhat tight.
Most of the AC solution has taken 0.5s+ time (in cpp).

71

just use fast unput bro ,they are not testing your logic ,they are just testing how do we efficiently use fast i/0

72

How to flagged this post?

73

Hello there, I changed your return type of dfs func from vector to void and it got accepted
https://www.codechef.com/viewsolution/34628746

1 Like
74

I was initially using testers’s approach of selecting vertices depending on ratio, this approach gave TLE in both DFS and BFS , I don’t know why.
Then I removed this extra loop and and checked ratio just by multiplying and got
AC in both DFS and BFS approach.

My DFS soltuion (AC):
https://www.codechef.com/viewsolution/34629111
MY BFS soltuion (AC):
https://www.codechef.com/viewsolution/34629095

75

My humble request to don’t include your micros in solutions. It’s very hard to understand for beginners.

2 Likes
76

here is my submission using DSU.
https://www.codechef.com/viewsolution/34631551

1 Like