SJ1 - Editorial

editorial
, , , ,
45

https://www.codechef.com/viewsolution/24041293

Please help
Can anyone point out problem in my code. I am getting TLE for all cases except 1 case. I have commented my code thoroughly.

46

Hi! Thanks for the question. Since you’re going to take coefficients modulo m_{l_i} in the end, it doesn’t matter. You may just take m-k instead of -k to obtain needed remainder.

47

I did not get the following things:

  1. Why is it assured the equation will have a solution if g/g’ and m/g’ are coprime?
  2. How can we substitute g with g’?

From the other answer, I can see that gcd is the interval which separates successive multiples of g’ but how can I prove that generally?
Any suggested reading that I should go through?

48

Pass graph “adj” by reference in your function. Everytime the function is called, graph is copied! Hence, TLE.

1 Like
49

Solution for linear diophantine equation with co-prime numbers may be obtained by extended euclidean algorithm. We may substitute g with g' because equation g'=kg \pmod{m} has a solution so set of numbers which occur in arithmetic progression of g is the same as set of numbers which occur in arithmetic progression of g'.

50

Tried almost everything, but getting runtime error for first 9 testcases

#include <bits/stdc++.h>
using namespace std;
#define ll long long
vector<int> tree[10001];
ll val[10001];
ll m[10001];
ll res[10001];
vector<ll> leaf;
ll _gcd(ll a, ll b){
    if(a<b)
    return _gcd(b,a);
    if(b==0)
    return a;
    return _gcd(b,a%b);
}
void cal(int x, int p, ll gcd){
    gcd = _gcd(gcd,val[x]);
    
    for(auto u: tree[x]){
            if(u==p)
                continue;
            cal(u,x,gcd);
        }
        
    if(tree[x].size()==1 && x!=1){
        leaf.push_back(x);
        res[x] = m[x]-_gcd(m[x],gcd);
    }
}
int main() 
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin>>t;
    while(t--)
    {
    	
        int n;
        cin>>n;
        if(!leaf.empty())
        leaf.clear();
        for(int i=1; i<=n; i++)
            tree[i].clear();
        int a,b;
        for(int i=0; i<n-1; i++){
            cin>>a>>b;
            tree[a].push_back(b);
            tree[b].push_back(a);
        }

        for(int i=1; i<=n; i++)
            cin>>val[i];
        for(int i=1; i<=n; i++)
            cin>>m[i];

        cal(1,0,val[1]);
        sort(leaf.begin(),leaf.end());
        int sz = leaf.size();
        for(int i=0; i<sz; i++)
            cout<<res[leaf[i]]<<" ";
        cout<<"\n";
    }
    return 0;
}
51

Your explanation made everything much easier. Thanks a lot for your patience and explanation.

52

you should be putting the if(G[i].size()==1) in DFS, outside the if(T[i] == false).

53

Could you explain why we chose undirected graph ?

54

input format says ‘there is an edge between x and y’ and not ‘there is an edge frm x to y’
hence input for was in that format thats why you shld choose undirected graph
assume the graph to be undirected if not given in ques for future probs

3 Likes
55

" since ,g/g’ and m/g’ are co-prime, this equation will always have a solution"but what if the solutions are negative because we know that this equation has a solution if gcd is 1. But it can be negative right?

56

The condition to check leaf node is wrong. If the root contains only one child, your condition will give true for this.

1 Like
57

I am getting AC for all testcases except 11th one ,can anyone tell me what is the mistake
https://www.codechef.com/viewsolution/34437483

58

@yuv_sust your explanation helped me a lot. Thank you!

59

Your explanation helped a lot to understand, I was about to leave this question before I saw your explanation. Thank you!

60

can someone find out why my code gives TLE .
https://www.codechef.com/viewsolution/46718475
thanks in advance .