Can someone tell me what is wrong in my pyth3.6 code

question:ICPC16B Problem - CodeChef
solution:
CodeChef: Practical coding for everyone

I requested you in this post to provide a submission link.
Also explain your solution briefly if you really want any sort of help from the community.

Finally, your code looks to be O(n^3) per test case. Think of a different solution or if you’re really stuck look at the editorial.

Edit:
Hint: If a and b are in the array then a*b is also in the array. If a and a*b are present in the array, a*a*b is also in the array.

1 Like

for:
1
2 3 4 5
your code gives : No

for:
1
5 2 3 4
your code gives: Yes.

See, why that is and debug your code.

1 Like

Hi @psaini72 @sikh_coder
please can you guys help me to find the reason for wrong answer

problem link

my approach is to use co-ordinate compression and dsu.

my solution

Solution
#include <bits/stdc++.h>

using namespace std;
int q;

int sz[1000100];
int rt[1000010];
void init(int n){
    for(int i=0;i<=n;i++){
        sz[i] = 1;
        rt[i] = i;
    }
}

int find(int x){
       
       while(x!=rt[x])x=rt[x];
       return rt[x];
}

void merge(int p,int q){

   int x = rt[p];
   int y = rt[q];
   if(x == y)return;
   
   if(sz[x] > sz[y])swap(x,y);
   sz[y]+=sz[x];
   sz[x] = 0;
   rt[x] = rt[y];
}

int main()
{

    cin >> q;
    vector<pair<int,int>>v(q);
    vector<int>aux;
    for(int i=0;i<q;i++)
    {
        int p,q;
        cin >> p >> q;
        aux.push_back(p);
        aux.push_back(q);
        v[i].first = p;
        v[i].second = q;
        
    }

    sort(aux.begin(),aux.end());
   map<int,int>mp;
    int cnt=1;
    for(int i=0;i<aux.size();i++){
        if(i==0 || aux[i]!=aux[i-1]){
            mp[aux[i]] = cnt++;
        } 
    }

    for(int i=0;i<q;i++){
       v[i].first = mp[v[i].first];
       v[i].second = mp[v[i].second];
    }

    init(cnt);

    for(int i=0;i<q;i++){

        merge(v[i].first, v[i].second);

        cout<<sz[find(v[i].first)]<<"\n";
    }


   
}


Don’t really understood your code:

here’s how I did it using weighted union and path compression:
I don’t think this a fancy problem or such.It’s fairly straightforward. The only thing is that here size is till 10^9. So, what does that tell you? don’t make an array. use a map. and that’s what I did.

https://www.hackerrank.com/challenges/friend-circle-queries/submissions/code/112958721

You are trolling aren’t you? :joy:

Open a separate topic. Don’t use this one. Provide a submission link (details tag is fine but I would still prefer a submission link). If you have already opened a topic and no one replied, just reply to it once again with something like “bump” so that is shows up on the home page and more people will look at it.

Edit: In your merge function, it should be int x = find(p) becuase after merging, you only update the roots of the roots. Not the whole tree. Could be that this is not the only error.

1 Like

Yes,that is why I used coordinate compression.

I was reading this post and it was on open tab and I asked ,I thought it’s fine to ask anywhere . But will do next time …:joy::joy:
Edit: thanks got it

I don’t think you need to do that here:

My Solution
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define fastio			std::ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define test int t;cin>>t;while(t--)

map<ll,ll> dsu;
ll max_len=INT_MIN;

map<ll,ll> size_ofSet;

int root(ll x) //path-compressed
{
	
	while(dsu.find(x)!=dsu.end() && dsu[x]!=x)
	{
		dsu[x]=dsu[dsu[x]];
		x=dsu[x];
	}
	return x;
}

void weighted_union(ll a,ll b) //weighted
{
	ll root_A=root(a);
	ll root_B=root(b);

	if(root_A==root_B) return;
	
	if(dsu[root_A]==0) dsu[root_A]=root_A;
	if(dsu[root_B]==0) dsu[root_B]=root_B;


	 //cout<<root_A<<" "<<root_B<<"\n";

	if(size_ofSet[root_A]==0) size_ofSet[root_A]=1;
	if(size_ofSet[root_B]==0) size_ofSet[root_B]=1;

	if(size_ofSet[root_A]>size_ofSet[root_B])
	{
		dsu[root_B]=dsu[root_A];
		size_ofSet[root_A]+=size_ofSet[root_B];

		max_len=max(max_len,size_ofSet[root_A]);
	}
	else
	{
		dsu[root_A]=dsu[root_B];

		size_ofSet[root_B]+=size_ofSet[root_A];

		max_len=max(max_len,size_ofSet[root_B]);
	}

}


int main() {
	
	fastio;
	test{

		ll a,b;cin>>a>>b;

		weighted_union(a,b);
		cout<<max_len<<"\n";
		
	}

	return 0;
}

thanks so if i write k=l+1 instead of k=1 than the output for the inputs you give will be correct but still it is showing wrong answer when i submit it so can you please tell me where i get it wrong