devol's blog

GCD and Simple path Problem in GFG
By devol, history, 4 years ago, In English

Link to the problem: https://practice.geeksforgeeks.org/contest/job-a-thon-for-internship/problems/#

ll dfs1(int src,int par,vector<int> val,ll dp1[],ll dp2[],int k,vector<vector<int>> adj){
    if(dp1[src]!=-1)return dp1[src];
    if(val[src]%k==0){
        ll ans=0;
        for(auto e:adj[src]){
            if(e!=par){
                ans+=dfs1(e,src,val,dp1,dp2,k,adj);
            }
        }

        dp1[src]=ans+1;
        dp2[src]=0;
        for(auto e:adj[src]){
            if(e!=par)
                dp2[src]+=((ans-dp1[e])*dp1[e]);
        }
        dp2[src]/=2;
        dp2[src]+=ans;
      //  cout << src << " " << dp2[src] << " " << ans << endl;
        return dp1[src];
    }
    else{
        dp1[src]=0;
        dp2[src]=0;

        for(auto e:adj[src]){
            if(e!=par){
                dfs1(e,src,val,dp1,dp2,k,adj);
            }
        }
        return dp1[src];
    }
}

long long countPairs(int N, vector<vector<int>> Edges, vector<int> Val,int K)
{
    vector<vector<int>> adj(N+5);
    ll dp1[N+1];
    memset(dp1,-1,sizeof dp1);
    for(auto e: Edges){
        int u=e[0];
        int v=e[1];
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    ll dp2[N+1];
    memset(dp2,0,sizeof dp2);
    dfs1(0,-1,Val,dp1,dp2,K,adj);

    int str=0;
    //cout << ans << endl;

    for(int i=0;i<N;i++){
        str+=dp2[i];
    }
    return str;
}

I have been trying to solve it but my solution either gives TLE or wrong answer and for this specific solution its TLE, Can anyone please find the error in my code and tell me the right approach. Thanks and regards

  • Vote: I like it
  • -22
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by devol (previous revision, new revision, compare).

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    Just count the connected components in which all nodes are divisble by k. And choose any two nodes and that path will contribute to your answer.

    → Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

In this problem, while moving from one vertex to another, you cannot cross a vertex whose value is not divisible by k, so just find all connected parts and add the number of possible pairs in the answer.

For example :

7 3
3 9 6 5 3 6 6
1 2
1 3
2 4
4 5
5 6
5 7

In the above testcase the value at 4 is not divisible by k so it divides the graph into 2 connected parts {1, 2, 3} and {5, 6, 7}. Thus answer will be (3 * 2) / 2 + (3 * 2) / 2.

→ Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I solve it using simple concept of connecting components. In isvalid condition also check weather the child on which we are going to call dfs is divisible by k or not. Count no of nodes in such components in each dfs call and then res+=count*(count-1)/2

My code

int k;
class Solution
{
    public:
    void dfs(vector<bool> &isvisited,vector<int> graph[],int node,long long &count,vector<int> &Val){
        isvisited[node] = true;
        count+=1;
        for(int child:graph[node]){
            if(!isvisited[child]&&Val[child]%k==0){
                dfs(isvisited,graph,child,count,Val);
            }
        }
    }
    
    
    long long countPairs(int N, vector<vector<int>> Edges, vector<int> Val,int K){
        // code here
        vector<int> grap[N+1];
        for(int i=0;i<Edges.size();i++){
            // cout<<Edges[i][0]<<" "<<Edges[i][1]<<endl;
            grap[Edges[i][0]].push_back(Edges[i][1]);
            grap[Edges[i][1]].push_back(Edges[i][0]);
        }
        // for(int i=0;i<N;i++){
        //     cout<<i<<" ";
        //     for(int child:grap[i]){
        //         cout<<child<<" ";
        //     }cout<<endl;
        // }
        vector<bool> isvisited(N+1,false);
        k = K;
        long long res = 0;
        for(int i=0;i<N;i++){
            if(!isvisited[i]&&Val[i]%k==0){
                long long count = 0;
                dfs(isvisited,grap,i,count,Val);
                // cout<<count<<endl;
                res+=(count*(count-1)/2);
            }
        }return res;
        
    }
};
→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I solved this problem using DSU.

You can see that some nodes have "Value" such that -> Val[node] % K == 0, Hence we observe that we can take any edge that connects node 'u' <-> 'v' where Val[u] % K == 0 AND Val[v] % K == 0.

So we simply traverse the 'Edges' vector and see if the above condition holds for 'u' and 'v' then we do :- union_operation(u, v), keep in mind to use "size optimization and path compression for fitting time limit".

After making such groups, we can traverse for all nodes [0, N — 1] and get their group leader (by using get_operation(node)), if this leader_node is visited (vis[leader_node] == true) then we shall continue our loop

OR Else

let then grpSize = size[leader_node] and mark vis[leader_node] = true (we are visiting this leader for the first time) and we simply pick any 2 nodes from this group (because a path will exist and all nodes shall be atleast divisible by k). So update you "ans" as : ans += (grpSize * (grpSize — 1)) / 2

(use long long in c++)

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In the same problem firstly i tried to pass the vectors and variables without reference then it was showing TLE (somehow got AC by many optimisation but time taken-1.98 sec)

But when i passed them by reference it resulted in AC (time-0.53sec),

can someone please explain why this happened.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If you pass without reference, the compiler makes the copy of all the vectors and variables again all the time you call the function, and hence when the compiler makes the copy of a string/vector of length/size n then that copy is made in O(n)...hence the extra time.

    Passing by reference is a good practice, it saves time and by reference means that the address of the passed variable will be stored....in the case of vector, it is simply the address of the first element, so you see its O(1).

    Hope I explained it okay :)

    → Reply
»
4 years ago, # |
  Vote: I like it -7 Vote: I do not like it

gfg bad,downvote

→ Reply