Thanks a lot @aneee004 for pointing that out. 
1 Like
Because of precision issues.
Refer this
You can avoid this by not dividing and working only with integers by cross multiplication.
this solution is giving RE but working fine with sample input and some random inputs i used for testing .
I tried asking this in several threads of codechef discussion but haven’t received any feedback.
really worried…please help me out guys … @aneesh2312 @dark_horse07 @sebastian @robosapien @ameybhavsar @dark_horse07
import collections
def dfs(p):
visited.add(p)
temp.add(p+1)
for node in road[p]:
if(node not in visited and selected[node]):
dfs(node)
t=int(input())
for _ in range(t):
n,m=map(int,input().split())
income=list(map(int,input().split()))
pop=list(map(int,input().split()))
road=collections.defaultdict(list)
for __ in range(m):
a,b=map(int,input().split())
road[a-1].append(b-1)
road[b-1].append(a-1)
i=income[0]
p=pop[0]
# to find max per capita
for x in range(1,n):
if(i*pop[x]<p*income[x]):
i=income[x]
p=pop[x]
selected=[False]*n
# to select node with max per capita
for x in range(n):
if(pop[x]*i== income[x]*p):
selected[x]=True
visited=set()
ans=set()
for each in range(n):
if(each not in visited and selected[each]):
temp=set()
dfs(each)
if(len(temp)>len(ans)):
ans=temp
print(len(ans))
print(*ans)Bro, I don’t know much about python. I don’t know why this is giving RE
can u provide some test cases so that can i can debug please …
i am new don’t how to generate it.
it will be kind if you tag someone who knows python and can help me out ?
please please…
Thanks! It helped.
1 Like
I am getting WA . Even after thinking for hours I can’t spot the mistake. Please help.
Here’s my solution CodeChef: Practical coding for everyone
You certainly have overflow while comparing ar1[i]*e > ar2[i]*w, use long long datatype.
1 Like
Thank you so much sir !
Now i can happily end the day after getting that green tick.
Thanks again for helping noobs like me.
1 Like
CodeChef: Practical coding for everyone still not getting accepted… even after using scanf and printf
Friends I am getting TLE. could someone help me please.
Your logic seems wrong-
-
For max you need double.
-
You don’t need to output gdp. You need to output chosen provinces.
-
However, it should also be possible to travel from each of the chosen provinces to any other chosen province without visiting any of the abandoned provinces.You are not following this condition.
Correct Logic-
You can easily decide max gdp and then take all nodes which have value equal to that gdp because you need to maximize the chosen provinces as well but all these provinces can’t be chosen as the graph may be disconnected. Choose that component that has maximum nodes
1 Like
thanks
can this question be done by using normal logic i.e. without using graphs
No, you need to know BFS/DFS (Graph Algorithms) to do this problem.
I really appreciate the fact the you took care of all the mistakes you were doing early.
You got rid of floating point values by cross multiplication (comparing integers).
Secondly, you also learnt Graph Algorithms to solve this problem.
The only flaws in your solution are:
You are required to print only those things which are asked in Problem. Like, cout<<num<<" "<<den<<endl; should be commented. You must have used it while debugging but you need to remove while submitting.
The second mistake is you are decrementing the nodes while taking input like in these lines- g[u-1].push_back(v-1); g[v-1].push_back(u-1);. While outputting you should increment them back as cout<<x+1<<" ";. Hope you understood your mistakes.
AC Code
#include <bits/stdc++.h>
#define int long long
#define endl "\n"
#define PI acos(-1.0)
#define Pi 3.141592653589793
#define SQR(n) ( n * n )
/// Math End
/// Pair Start
#define F first
#define S second
#define mp make_pair
/// Pair End
/// Array Start
#define SET(a) memset( a, -1, sizeof a )
#define CLR(a) memset( a, 0, sizeof a )
#define MEM(a,val) memset( a, val, sizeof(a) )
/// Array End
/// Extra Start
#define pb push_back
#define SS stringstream
#define ull unsigned long long
#define mod 1000000007
#define INF 2147483647
#define SIZE 2000001
#define _cin ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
vector<int> paths;
int32_t main() {
_cin
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int t;
cin>>t;
while(t--){
int n,m;
cin>>n>>m;
vector<int> a(n),b(n);
int x;
for(auto &i: a) {
cin>>x;
i = x;
}
for(auto &i: b) {
cin>>x;
i = x;
}
vector<int> g[n];
for(int i=0; i<m; i++) {
int u,v;
cin>>u>>v;
g[u-1].push_back(v-1);
g[v-1].push_back(u-1);
}
int num=a[0];
int den=b[0];
for(int i=0; i<n; i++)
{
if(a[i]*den > b[i]*num)
{
den=b[i];
num=a[i];
}
}
// cout<<num<<" "<<den<<endl;
vector<int>v(n,0);
vector<int>ans;
for(int i=0; i<n; i++)
{
if(v[i]==0 && (num*b[i]== den*a[i]))
{
queue<int>q;
q.push(i);
vector<int>temp;
v[i]=1;
while(q.empty()!=true)
{
int top=q.front();
q.pop();
temp.push_back(top);
for(auto x:g[top])
{
if(v[x]==0 && num*b[x]== den*a[x])
{
q.push(x);
v[x]=1;
}
}
}
if(temp.size()>ans.size())
{
ans=temp;
}
}
}
cout<<ans.size()<<endl;
for(auto x:ans)
{
cout<<x+1<<" ";
}
cout<<endl;
}
return 0;
}
If you prefer link
Notice the changes in the above codes.
2 Likes