TLE in Dish Owner

help
1

Getting tle for the problem :- CodeChef: Practical coding for everyone
My solution :- CodeChef: Practical coding for everyone

2

Hey @abhay_2012. I solved it with DSU (Submission). This should help you check if the algorithm is correct.
Maybe there’s a bug in your DSU root and merge function.

3 
inline int root(int x){
    while(x!=A[x]){
        x=A[x];
    }
    return x;
}

This is an O(N) function, I guess.

You might want to rewrite it using Path Compression, which looks like this:

inline int root(int x) {
    while(x != A[x]) {
        A[x] = A[A[x]];
        x = A[x];
    }
    return x;
}
2 Likes
4

Hi @suman_18733097

from collections import defaultdict as dd
n=int(input())
for i in range(n):
    m=int(input())
    s=list(map(int,input().split()))
    d=dd()
    e=dd()
    f=dd(list)
    for j in range(1,m+1):
        d[j]=s[j-1]
        e[j]=j
        f[j].append(j)
        
    q=int(input())
    for j in range(q):
        l=[]
        l=list(map(int,input().split()))
        if l[0]==0:
            x,y=l[1],l[2]
            if e[x]==e[y]:
                print("Invalid query!")
            elif d[x]==d[y]:
                continue
            else:
                if d[x]>d[y]:
                    for k in f[y]:
                        e[k]=e[x]
                        f[e[x]].append(k)
                else:
                    for k in f[x]:
                        e[k]=e[y]
                        f[e[y]].append(k)
        else:
            print(e[l[1]])

for the same question iam getting WA …i tried few inputs they passed correctly… Any idea where iam going wrong?

5

This is not the way you solve this problem. You might want to learn Union-Find Data Structure (often called Disjoint set union) to solve this problem.

6

Yeah agreed but even this logically solves correct?

7

You might want to share your approach as well. It is difficult to understand your code.

8

Created 3 dictionaries:
d—stores the scores of the dish
e-stores the owner of particular dish
f- stores all the dishes that the owner has

first iam checking for if it related to same user or e[x]!=e[y]

second seeing if both dish have same score
third looping through the list of f for the owner whose score is less and adding to the other owner

9

Thanks

10

CodeChef: Practical coding for everyone still tle

11

I am not able to find the bug.

12

I wonder why you messed up again. (The only reason I could think of is: He’s one of the best participants of Long Challenge).

ACfied Code: 
#include <bits/stdc++.h>
using namespace std;
int A[10001],S[10001];
void init(int n){
    for(int i=1;i<=n;i++){
        A[i]=i;
    }
}

inline int root(int x){
    while(x!=A[x]){
        A[x]=A[A[x]];
        x = A[x];
    }
    return x;
}

inline void merge(int x,int y){
    int rootA=root(x);
    int rootB=root(y);
    
    if(rootA!=rootB){
        if(S[rootA]==S[rootB])return;
        if(S[rootA]>S[rootB]){
            A[rootB]=rootA;
        }else{
            A[rootA]=rootB;
        }
    }else{
        cout<<"Invalid query!\n";
    }
}
int main() {
	// your code goes here
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t;
	cin>>t;
	while(t--){
	    int n;
	    cin>>n;
	    
	    for(int i=1;i<=n;i++){
	        A[i]=i;
	        cin>>S[i];
	    }
	    
	    int q;
	    cin>>q;
	    
	    while(q--){
	        int ch;
	        cin>>ch;
	        
	        if(ch==1){
	            int x;
	            cin>>x;
	            cout<<root(x)<<"\n";
	        }else{
	            int x,y;
	            cin>>x>>y;
	            merge(x,y);
	        }
	    }
	}
	return 0;
}

Submission link: CodeChef: Practical coding for everyone

1 Like
13

thanks… i got the idea.