I used the same approach but got WA during contest…
i just changed the method of comparison now and it got accepted
so instead of storing the value income/population
store numerator and denominator and compare using them only.
WA code : CodeChef: Practical coding for everyone
AC code : CodeChef: Practical coding for everyone
such things really hurt 
I used the same approach . could not able to find wrong test case.
https://www.codechef.com/viewsolution/34622010
Video Editorial.
Can anybody help on why I am getting runtime error on this? I almost followed the editorial and it passed the sample test cases + my weak(simple) test cases.
https://www.codechef.com/viewsolution/34616966
A test case with answer where the code shows runtime error is all I need! Thanks in advance.
I have used FAST IO
Would’nt that suffice?
My code gave TLE in PyPy 3. I tried to optimize a lot to get AC. Finally after frustration, I submitted the same code in Python 3 and it gave AC. Now After the contest the same code is giving AC in both PyPy 3 and Python 3. Waiting for rating drop. 
as per the constraints, N>=1, M>=1 and u[i] != v[i]
So for n=1,there can’t be any edge but still we need to add one as per the constraints(bcoz M>=1). @taran_1407 can you please clarify this or is this a typing error ?
DFS explanation video tutorial.
Did anyone got ACusing DSU and storing numerator/denominator values in double?
my code gives WA->7VoHLS - Online C++0x Compiler & Debugging Tool - Ideone.com
Any help will be appreciated.Thanks in advance…
Seems like a lot of DFS solutions are getting TLE.
https://www.codechef.com/viewsolution/34618521
My logic is correct but I am getting NZEC. It would be really helpful if somebody could point out the mistkae.
Hi akshitm, same here brother. I tried DFS recursive (with setrecursionlimit to 10**6). Then I tried DFS iterative in the contest… Both gave TLE using pypy
I tried many other optimizations. But still got TLE. This is infuriating. If the problem cannot be solved using pypy/python in given constraints…they should mention it.
Even I got TLE
My code gave AC in Python after many attempts in PyPy. So, your statement the problem cannot be solved using pypy/python in given constraints is false.
Here is my solution that I have implemented using BFS.
https://www.codechef.com/viewsolution/34623172
This got AC.
I implemented the same thing using BFS, but have only inserted those vertexes to the adjacency list whose percapita is equal to the maximum percapita.
This got TLE.
https://www.codechef.com/viewsolution/34621844
Can anyone please explain why? Thanks
You are using floating point arithmetic. At some point there can be precision loss. Use an integer data type to compare. See setters code or my submission.
ALWAYS AVOID FLOATING POINT ARITHMETIC IF IT’S POSSIBLE!
I am sure python/pypy solution gave TLE during contest. Please either regrade or remove that question from ranking list. I tried optimizing my code for it. It always gave TLE. If the problem cannot be solved in a specific language for given constraints then why can’t you clearly mention it?
Two of my submission attempts:
https://www.codechef.com/viewsolution/34623632
CodeChef: Practical coding for everyone (Accepted after contest) But clearly not within the 1 second constraint. I am sure this can’t go from 3.87 to 1 second …I have tried dfs recursive/iterative/stdin input …every possible optimization I could think of.
So back to my main point. You could have clearly stated this problem constraints was only for optimized C++. And don’t both wasting time trying to do it in python. Rating is going to fall now 
Why this code is giving TLE?
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<cmath>
#include<bitset>
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define N 1000000
double income[N],pop[N];
double ans =0;
ll vis[N];
ll size;
vector<ll> final;
void dfs(vector<vector<ll>> a,ll c,)
{
vis[c]=1;
for(ll i=0;i<a[c].size();i++)
{
if(vis[a[c][i]]==0)
{
dfs(a,a[c][i]);
}
}
}
main()
{
ll t;
cin>>t;
while(t--)
{
ll n,m;
cin>>n>>m;
vector<vector<ll>> a(n,vector<ll>());
for(ll i=0;i<n;i++)cin>>income[i];
for(ll i=0;i<n;i++)cin>>pop[i];
for(ll i=0;i<m;i++)
{
ll u,v;
cin>>u>>v;
u--;
v--;
a[u].push_back(v);
a[v].push_back(u);
}
double avg[n];
vector<pair<double,ll> >vx;
double mv =0;
ll ind;
for(ll i=0;i<n;i++)
{
avg[i] = (double)income[i]/(double)pop[i];
// vx.push_back({avg[i],i});
if(mv<avg[i])
{
mv=avg[i];
ind=i;
}
}
vector<ll> possible;
possible.push_back(ind);
for(ll i=0;i<n;i++)
{
if(i==ind)
continue;
if(fabs(avg[i]-avg[ind])<0.0000001f)
{
// cout<<i<<"add"<<endl;
possible.push_back(i);
}
}
if(possible.size()==1)
{
cout<<mv<<endl;
cout<<possible[0]+1<<endl;
continue;
}
for(ll i=0;i<n;i++)
vis[i]=0;
vis[ind]=1;
dfs(a,avg[ind],ind,n,vector<ll>());
cout<<mv<<endl;
for(ll i=0;i<possible.size();i++)
{
if(vis[possible[i]]==1)
cout<<possible[i]+1<<" ";
}
cout<<endl;
}
}
MOdify by eleminating some extra logic but still it giving TLE
PLease help
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<cmath>
#include<bitset>
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define N 1000000
double income[N],pop[N];
double ans =0;
ll vis[N];
ll cc[N];
ll size;
vector<ll> final;
void dfs(vector<vector<ll>> a,ll c)
{
vis[c]=1;
for(ll i=0;i<a[c].size();i++)
{
if(vis[a[c][i]]==0 && cc[a[c][i]]==1 )
{
dfs(a,a[c][i]);
}
}
}
int main()
{
ll t;
cin>>t;
while(t--)
{
ll n,m;
cin>>n>>m;
vector<vector<ll>> a(n,vector<ll>());
for(ll i=0;i<n;i++)cin>>income[i];
for(ll i=0;i<n;i++)cin>>pop[i];
for(ll i=0;i<m;i++)
{
ll u,v;
cin>>u>>v;
u--;
v--;
a[u].push_back(v);
a[v].push_back(u);
}
double avg[n];
double mv =0;
ll ind;
for(ll i=0;i<n;i++)
{
avg[i] = (double)income[i]/(double)pop[i];
cc[i]=0;
if(mv<avg[i])
{
mv=avg[i];
ind=i;
}
}
ll possible=1;
for(ll i=0;i<n;i++)
{
if(i==ind)
continue;
if(fabs(avg[i]-avg[ind])<0.0000001f)
{
cc[i]=1;
possible++;
}
}
if(possible==1)
{
cout<<mv<<endl;
cout<<ind+1<<endl;
continue;
}
for(ll i=0;i<n;i++)
vis[i]=0;
vis[ind]=1;
dfs(a,ind);
cout<<mv<<endl;
for(ll i=0;i<n;i++)
{
if(vis[i]==1)
cout<<i+1<<" ";
}
cout<<endl;
}
return 0;
}