PERCAPTA - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2

Setter: Rezwan Arefin
Tester: Raja Vardhan Reddy
Editorialist: Taranpreet Singh

DIFFICULTY:

Easy

PREREQUISITES:

Basic Maths, DSU, or DFS/BFS on a graph (flood fill).

PROBLEM:

Given a graph with N nodes (represented by cities) and M bidirectional edges (represented by roads between cities). Each city has a given total annual income (given by A_i) and a population (given by B_i).

You are required to find the largest connected subgraph such that the per capita income of the chosen subgraph is maximum possible.

QUICK EXPLANATION

  • We only choose those cities into subgraph which have the largest per capita income. We discard the rest.
  • After discarding, the largest connected component of the remaining cities is the largest possible connected subgraph we can get, which has maximum per capita income.

EXPLANATION

First, let us consider two cities 1 and 2, such that the annual income of cities are A and C, and the populations of cities are B and D respectively. WLOG assume \displaystyle\frac{A}{B} < \frac{C}{D}.

Then, if we decide to keep the both cities, the resulting per capita income shall be \displaystyle\frac{A+C}{B+D}. But we know that \displaystyle\frac{A}{B} < \frac{A+C}{B+D} < \frac{C}{D} holds.

You can find the mathematical proof here, I’ll explain how to theoretically interpret this.

See, Say E =\displaystyle \frac{A}{B} and F = \displaystyle\frac{C}{D}, then we can see that the per capita income of subgraph with above two cities must lie between E and F.

Proof by contradiction

Let’s assume the per capita income of the graph containing both cities, is less than \displaystyle\frac{A}{B}.
This means \displaystyle\frac{A+C}{B+D} < \frac{A}{B}
We get (A+C)*B < A*(B+D), giving C*B < A*D which implies \displaystyle\frac{C}{D} < \frac{A}{B}, but this goes against our assumption, hence \displaystyle\frac{A+C}{B+D} > \frac{A}{B}

We can similarly prove \displaystyle\frac{A+C}{B+D} < \frac{C}{D}

Hence, selecting a single city u with maximum \displaystyle\frac{A_u}{B_u} gives the best per capita income, so any city v with \displaystyle\frac{A_v}{B_v} < \frac{A_u}{B_u} are never included in final subgraph. So, let’s remove all such cities from graph.

Now we are left with the problem to select the largest number of cities such that each node in the selected subset is reachable from each other. We can easily use either DFS or Disjoint Set Union to find the largest connected component in the remaining graph.

For the DSU approach, we also need to keep track of the size of each component, or we can just find the frequency of each root (termed as the leader on the cp-algorithms page) and choose all the nodes whose root has a maximum frequency.

TIME COMPLEXITY

For the DFS solution, the time complexity is O(N) per test case.
For the DSU solution, the time complexity is O(N*\alpha(N)) per test case where \alpha(N) is Inverse Ackermann function

SOLUTIONS:

Setter's solution
#include  <bits/stdc++.h>
using namespace std;

using ll = long long;
using ii = pair<long long, long long>;
const int maxn = 2e5 + 5;

int n, m, par[maxn], sz[maxn];

int find(int u) {
	return par[u] == u ? u : par[u] = find(par[u]);
}

void unite(int u, int v) {
	u = find(u), v = find(v);
	if(u == v) return;
	if(sz[u] > sz[v]) swap(u, v);
	sz[v] += sz[u];
	par[u] = v;
}

int main(int argc, char const *argv[]) {
	// freopen("in", "r", stdin);
	int t; 
	scanf("%d", &t); 
	while(t--) {
		scanf("%d %d", &n, &m);
		for(int i = 0; i <= n; ++i) par[i] = sz[i] = 0; 

		vector<ii> R(n);
		ii opt(0, 1);
		for(int i = 0; i < n; i++) {
			scanf("%lld", &R[i].first);
		}
		for(int i = 0; i < n; i++) {
			scanf("%lld", &R[i].second);
			int g = __gcd(R[i].first, R[i].second);
			R[i].first /= g;
			R[i].second /= g;
			if(opt.first * R[i].second < R[i].first * opt.second) {
				opt = R[i];
			}
		}
		for(int i = 0; i < n; i++) {
			par[i] = i, sz[i] = 1;
		}
		for(int i = 0; i < m; i++) {
			int u, v;
			scanf("%d %d", &u, &v);
			u--, v--;
			if(R[u] == opt and R[v] == opt) {
				unite(u, v);
			}
		}
	  
		int mx_sz = 0, arg = -1;
		for(int i = 0; i < n; i++) {
			int rep = find(i);
			if(sz[rep] >= mx_sz) {
				mx_sz = sz[rep];
				arg = rep;
			}
		}

		printf("%d\n", mx_sz);
		for(int i = 0; i < n; i++) {
			if(find(i) == arg) {
				printf("%d ", i + 1);
			}
		} putchar('\n');
	}
	return 0;
}
Tester's Solution (uses DFS approach)
//raja1999

//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")

#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string> 
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip> 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
//setbase - cout << setbase (16)a; cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 <<endl;prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val

using namespace std;
using namespace __gnu_pbds;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define int ll

typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;


//std::ios::sync_with_stdio(false);
int vis[200005],choose[200005],a[200005],b[210005];
vector<vi>adj(200005);
vi provinces;
vi res;
int dfs(int u){
	vis[u]=1;
	int i;
	provinces.pb(u);
	rep(i,adj[u].size()){
		if(vis[adj[u][i]]==0 && choose[adj[u][i]]==1){
			dfs(adj[u][i]);
		}
	}
}
main(){
	std::ios::sync_with_stdio(false); cin.tie(NULL);
	int t;
	cin>>t;
	while(t--){
		int n,m,i,u,v,ans=0,num,den,max_id;
		provinces.clear();
		res.clear();
		cin>>n>>m;
		rep(i,n){
			adj[i].clear();
			vis[i]=0;
			choose[i]=0;
			cin>>a[i];
		}
		rep(i,n){
			cin>>b[i];
		}
		rep(i,m){
			cin>>u>>v;
			u--;
			v--;
			adj[u].pb(v);
			adj[v].pb(u);
		}
		num=a[0];
		den=b[0];
		f(i,1,n){
			if(a[i]*den>num*b[i]){
				num=a[i];
				den=b[i];
			}
		}
		rep(i,n){
			if(a[i]*den==num*b[i]){
				choose[i]=1;
			}
			else{
				choose[i]=0;
			}
		}
		fd(i,n-1,0){
			if(vis[i]==0 && choose[i]==1){
				provinces.clear();
				dfs(i);
				if(provinces.size()>res.size())
					res=provinces;
			}
		}
		cout<<res.size()<<endl;
		int siz=res.size();
		// fd(i,siz-1,0){
		random_shuffle(all(res));
		rep(i,siz){
			cout<<res[i]+1<<" ";
		}
		cout<<endl;
	}
	return 0;
} 
Editorialist's Solution (uses DSU approach)
import java.util.*;
import java.io.*;
class PERCAPTA{
	//SOLUTION BEGIN
	void pre() throws Exception{}
	void solve(int TC) throws Exception{
	    int N = ni(), M = ni();
	    long[] A = new long[N], B = new long[N];
	    for(int i = 0; i< N; i++)A[i] = nl();
	    for(int i = 0; i< N; i++)B[i] = nl();
	    long num = 0, den = 1;
	    int[] set = new int[N], sz = new int[N];
	    for(int i = 0; i< N; i++){
	        set[i] = i;sz[i] = 1;
	        if(A[i]*den > num*B[i]){
	            num = A[i];
	            den = B[i];
	        }
	    }
	    for(int i = 0; i< M; i++){
	        int u = ni()-1, v = ni()-1;
	        if(A[u]*den == B[u]*num && A[v]*den == B[v]*num){//If edge connects two maximum per capita income nodes
	            if(find(set, u) != find(set, v)){
	                sz[find(set, u)] += sz[find(set, v)];
	                set[find(set, v)] = find(set, u);
	            }
	        }
	    }
	    int root = 0;
	    for(int i = 0; i< N; i++)if(sz[find(set, i)] > sz[root])root = find(set, i);//finding largest sized component
	    pn(sz[root]);
	    for(int i = 0; i< N; i++)if(find(set, i) == root)p(1+i+" ");pn("");
	}
	//Union disjoint sets with path compression
	int find(int[] set, int u){
	    return set[u] = set[u] == u?u:find(set, set[u]);
	}
	//SOLUTION END
	void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
	static boolean multipleTC = true;
	FastReader in;PrintWriter out;
	void run() throws Exception{
	    in = new FastReader();
	    out = new PrintWriter(System.out);
	    //Solution Credits: Taranpreet Singh
	    int T = (multipleTC)?ni():1;
	    pre();for(int t = 1; t<= T; t++)solve(t);
	    out.flush();
	    out.close();
	}
	public static void main(String[] args) throws Exception{
	    new PERCAPTA().run();
	}
	int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
	void p(Object o){out.print(o);}
	void pn(Object o){out.println(o);}
	void pni(Object o){out.println(o);out.flush();}
	String n()throws Exception{return in.next();}
	String nln()throws Exception{return in.nextLine();}
	int ni()throws Exception{return Integer.parseInt(in.next());}
	long nl()throws Exception{return Long.parseLong(in.next());}
	double nd()throws Exception{return Double.parseDouble(in.next());}

	class FastReader{
	    BufferedReader br;
	    StringTokenizer st;
	    public FastReader(){
	        br = new BufferedReader(new InputStreamReader(System.in));
	    }

	    public FastReader(String s) throws Exception{
	        br = new BufferedReader(new FileReader(s));
	    }

	    String next() throws Exception{
	        while (st == null || !st.hasMoreElements()){
	            try{
	                st = new StringTokenizer(br.readLine());
	            }catch (IOException  e){
	                throw new Exception(e.toString());
	            }
	        }
	        return st.nextToken();
	    }

	    String nextLine() throws Exception{
	        String str = "";
	        try{   
	            str = br.readLine();
	        }catch (IOException e){
	            throw new Exception(e.toString());
	        }  
	        return str;
	    }
	}
}

Feel free to share your approach. Suggestions are welcomed as always. :slight_smile:

26 Likes

Can you tell corner cases? I applied the case approach but i am getting wa .

Enjoyed this problem.

2 Likes

I did BFS with this…sorted the array on bases of A/B and then started BFS form all childs in max order of A/B…take the child in bfs it gives increased AVG…and then check if else…getting Runtime error …Anybody can tell where I might be getting RE…let the approach be wrong…
Edit1: Almost did the same of EDITORIAL

Can someone please give some corner test cases, because I tried with both dfs and dsu but still getting WA :confused:

Getting TLE. Can someone point out why?
Submission link : https://www.codechef.com/viewsolution/34619486

3 Likes

applied the same approach,but getting wa,is there any corner case?

Can anyone tell me whats wrong with this solution ? https://www.codechef.com/viewsolution/34619137

Applied the Same Approach, But getting TLE
Please help
https://www.codechef.com/viewsolution/34621506

Did the same approach, yet received WA.
Can somebody help? https://www.codechef.com/viewsolution/34616520

I tried DFS approach and although my logic had some holes, I was unable to understand why I was getting runtime error. Can anyone please explain why, by looking at my solution.

SOLUTION

try using scanf and printf for i/o.

Enjoyed this problem very much, kudos to the setter🙌🏻

4 Likes

this is one of the poorly composed problem based on time limit.
https://www.codechef.com/viewsolution/34595547
https://www.codechef.com/viewsolution/34611537
in one solution i have used global array and in other i have used local later gets accepted and former doesn’t i think this should be looked.

3 Likes

Used the same approach as the editorial as far as I know my code.

But I am not getting any idea as to where it’s going wrong.

Please see it once and tell if you observe any test case where it goes wrong.

1 Like

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 : https://www.codechef.com/viewsolution/34620810
AC code : https://www.codechef.com/viewsolution/34622145

such things really hurt :frowning_face:

2 Likes

I used the same approach . could not able to find wrong test case.
https://www.codechef.com/viewsolution/34622010


Video Editorial.:slightly_smiling_face::slightly_smiling_face:
1 Like

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?