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. 
1 Like
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…
1 Like
Seems like a lot of DFS solutions are getting TLE.
1 Like
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.
1 Like
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.
1 Like
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!
2 Likes
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;
}
Done exactly as stated by @taran_1407 orz.
AC in 0.35 s. Again proving why C++ is so much better than Python for CP.
2 Likes
I agree…I need to shift to cpp now.
1 Like
Definitely you should brother. Python may seem very handy for easy, easy-medium questions, but when it comes to strict time-limits and long implementations, there’s no beating C++.
2 Likes