I went through the exact same train of thought. I was not even able to submit one question during the contest because of that! 
.
Easy problems in codechef doesnāt mean very easy. Very easy problems are tagged as beginner and cakewalk I guess. I generally relate to codechef easy problems as easy-medium.
And this problem is actually very easy if you have the knowledge of DSU. implementation with dfs and bfs is not very easy.
Sample case was passing so i had no idea where i was going wrong.
1 Like
Damn. You implemented that? I was stuck and couldnāt think of an algorithm for the misunderstood question. So I never had a chance to test the sample input :3.
Probably wrong implementation iām guessing now.
1 Like
Could you tell how after making a graph with all the nodes can we discard some nodes and keep the remaining nodes?
Please reply.
wrong ans even though my logic is same just like editorial,can anyone please help me?
https://www.codechef.com/viewsolution/34604725
https://www.codechef.com/viewsolution/34650702
I replaced cout/cin with printf/scanf and it got accepted , it should be looked too.
I Havenāt used DSU or DFS to Solve this problem.
I am only finding the maximum percapita income and if that max. percapita income are multiple , i am only considering all of them and just printing them in my solution.
But with this approach i am Getting WA.
My Solution-Click Here
Can Anybody Tell me where i am going wrong?
The regions must be connected. There might be disconnected regions if you do it like that.
Why is my code getting WA? Can someone help me?
#include <bits/stdc++.h>
#include <chrono>
#define ll long long int
#define ull usigned long long int
#define pb push_back
#define FASTIO cin.tie(0); ios_base::sync_with_stdio(false)
using namespace std;
const int MOD = 1e9 + 7;
const int maxN = 2e5 + 10;
struct Timer{
chrono::high_resolution_clock::time_point start, end;
chrono::duration<double> duration;
Timer(){
start = chrono::high_resolution_clock::now();
}
~Timer(){
end = chrono::high_resolution_clock::now();
duration = end - start;
cout << "Time : " << duration.count() << "s\n";
}
};
ll gcd(ll a, ll b){
if(a == 0){
return b;
}
return gcd(b % a, a);
}
ll powx(ll n, ll p){
ll res = 1;
while(p){
if(p & 1){
res = (res * n) % MOD;
--p;
}
else{
n = (n * n) % MOD;
p /= 2;
}
}
return res;
}
bool myswap(const pair<float, int> a, const pair<float, int> b){
if(a.first == b.first){
return a.second < b.second;
}
return (a.first > b.first);
}
bool visited[maxN + 1];
vector <int> adj[maxN + 1];
vector <int> idx;
bool choose[maxN + 1];
vector <int> temp, ans;
void init(){
memset(visited, 0, sizeof(visited));
memset(choose, 0, sizeof(choose));
idx.clear();
temp.clear();
ans.clear();
}
void dfs(int u){
for(int i = 0; i < adj[u].size(); ++i){
if(!visited[adj[u][i]] && choose[adj[u][i]]){
visited[adj[u][i]] = 1;
temp.pb(adj[u][i]);
dfs(adj[u][i]);
}
}
}
void solver(){
init();
int n, m, u, v;
cin >> n >> m;
float a[n], b[n];
vector <pair<float, int>> p;
for(int i = 0; i < n; ++i){
scanf(" %f", a + i);
}
for(int i = 0; i < n; ++i){
scanf(" %f", b + i);
p.pb({a[i]/b[i], i + 1});
}
for(int i = 0; i < m; ++i){
scanf(" %d %d", &u, &v);
adj[u].pb(v);
adj[v].pb(u);
}
sort(p.begin(), p.end(), myswap);
float max_v = p[0].first;
idx.pb(p[0].second);
choose[p[0].second] = 1;
for(int i = 1; i < n; ++i){
if(p[i].first == max_v){
choose[p[i].second] = 1;
idx.pb(p[i].second);
}
else{
break;
}
}
for(int i = 0; i < idx.size(); ++i){
if(!visited[idx[i]]){
visited[idx[i]] = 1;
temp.pb(idx[i]);
dfs(idx[i]);
}
if(temp.size() > ans.size()){
ans = temp;
}
temp.clear();
}
printf("%ld\n", ans.size());
for(int i = 0; i < ans.size(); ++i){
printf("%d ", ans[i]);
}
cout << '\n';
}
int main(){
int tc;
cin >> tc;
while(tc--){
solver();
}
return 0;
}Yeah i got it Brother.Later On, i read this line:
āthere is atmost one road between each pair of provincesā
In place of āatmostā if it would be written āatleastā then i think my approach would be right.
Thanks a lot
1 Like
#include <bits/stdc++.h>
using namespace std;
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define rep(i,a,b) for(int i=a; i<b; i++)
#define pb push_back
#define ll long long
vector<vector<int>> components;
void addEdge(vector<int> adj[], int u, int v)
{
adj[u].pb(v);
adj[v].pb(u);
}
vector<bool> used;
vector<int> city;
void dfs(vector<int> adj[], vector<int> cities, int u)
{
if(used[u] || !binary_search(cities.begin(), cities.end(), u)) return;
used[u] = true;
city.pb(u);
for(int v : adj[u])
{
dfs(adj, cities, v);
}
}
int main()
{
FASTIO
int t;
cin >> t;
while(t--)
{
int n, m;
cin >> n >> m;
components.clear();
used.assign(n, false);
vector<ll> a(n), b(n);
rep(i,0,n) cin >> a[i];
rep(i,0,n) cin >> b[i];
vector<int> adj[n];
rep(i,0,m)
{
int u, v;
cin >> u >> v;
addEdge(adj, u-1, v-1);
}
//Finding max per-capita income
ll num = a[0], den = b[0];
rep(i,1,n)
{
if(a[i]*den > b[i]*num)
{
num = a[i];
den = b[i];
}
}
//Marking all the nodes with the maximum per-capita income
vector<int> cities;
rep(i,0,n)
{
if(a[i]*den == b[i]*num) cities.pb(i);
}
// for(int x : cities) cout << x << " ";
// cout << "\n";
for(int u : cities)
{
if(!used[u])
{
dfs(adj, cities, u);
components.pb(city);
}
city.clear();
}
// for(auto x : components)
// {
// for(auto y : x) cout << y << " ";
// cout << "\n";
// }
//Finding the largest component
int max_len = 0;
rep(i,0,components.size())
{
if(components[i].size() > components[max_len].size())
max_len = i;
}
cout << components[max_len].size() << "\n";
for(auto k : components[max_len]) cout << k+1 << " ";
cout << "\n";
}
return 0;
}
Can anyone please help me eliminate TLE? And is my code correct?
You are passing the adjacency list and also the cities by value. So each time you call the function a copy of the vector is made and, thatās an additional O(n), where n is the vector size. Itās good to pass it by reference, and even better to just have these as global vectors. Your accepted solution is here.
1 Like
The video editorial for this problem is here:
Checkout codechef cook off problem - per capita income detailed explanation
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)