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
Codechef stills give 5X for Python (though Python may TLE within that range as well) but Codeforces doesnāt give any multiplier to Python. Secondly, implementation of most of the tough topics is only given in cpp and as always cpp is fast. So, youāre right.
Actually, the time multiplier for PYPY is 2, but for Pyhton 3. itās 5. Thatās why you got accepted submitting in Pyhton 3 but not in PYPY.