PERCAPTA - Editorial

editorial
, , , , ,
46

Faced similar issue man :frowning:

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

47

But PyPy is faster than Python. So, that is why Multiplier of PyPy is less. My Solution in PyPy gave TLE during the contest and got accepted in Python. Now the same solution after the contest is giving AC in both.

48
49

Can someone explain me this test-case ?

1
4 4
10 1 2 100000000
5 1 1 1
1 2
2 3
1 3
2 4

We are not considering 2nd node as explained above but if I considered 2nd node then I can consider 4th node as well and it will increase per capita income

Not considering 2nd node:
X = (10+2)/(5+1)

Considering 2nd and 4th node:
Y = (10+2+1+100000000)/(5+1+1+1)

Clearly, Y > X

@taran_1407
@rezwanarefin01
@raja1999

50

Why don’t you consider 100000000/1 ??

2 Likes
51

Can someone help. I did exactly the same thing as the editorial. Used BFS approach. Here is my solution.

52

I got wa when I used double and got ac by using long double

53

That’s nice. But sometimes you can lose precision even with long double. So it’s always best to use integer comparison if it’s possible.

54

You must have done something else wrong, because I got AC on double.

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?