SJ1 - Editorial

easy
editorial
gcd
number-theory
april19

#23

This explanation is really intuitive
.


#24

I guess you are missing taran’s editorials more - I barely get time to serve as editorialist these days I am sure people would have forgotten how mine were like :stuck_out_tongue:


#25

Thank you so much for the explanation! This is so easy to understand!:grin:


#26

thumbs up… it’s a great explanation, I see nowadays that the official editorials use a bit tough language and statements i.e. it’s not beginner friendly :frowning:


#27

"Life is too short to keep track of unwanted things"… :stuck_out_tongue: but seriously though I miss Chef’s Vijju Corner.


#28

@melfice It is mentioned in editorial that :

we always may find a linear combination which is equal to g , by extended euclids algorithm

But in extended Euclid’s theorem the coefficients of a,b maybe negative i.e in the equation ax+by=gcd(a,b) , x and y maybe negative .

However it is clearly mentioned in the question

"For each node on this path (including the root and this leaf), choose a non-negative integer and multiply the value of this node by it "


#30

what is wrong in this code.please if you can debug it
https://www.codechef.com/viewsolution/24013940


#31

now i am able to understand it clearly,thanks man


#32

@yuv_sust I agree that if D is not a multiple of G then surely there is no integral solution, however, I don’t see why the converse part is always true, that given any D=nG we can always get non-negative coefficients A, B, C... which satisfy the equation.
A simple example can be x=240 and y=46 with GCD(x,y) =G= 2 , lets say we want D=G (i.e n=1) here using extended Euclid’s theorem give us A=-9 and B=47 ( -9*240+47*46=2 ) , but in question it is clearly mentioned that the coefficients A,B with which we are multilpying the nodes must be positive.

"For each node on this path (including the root and this leaf), choose a non-negative integer and multiply the value of this node by it "


Unofficial Editorial of SJ1
#34

Please Help me with this code.
It is giving me wrong answer in every test case.
But i manually tested a few cases, they’re running fine.

#include<iostream>
#include<vector>
#include<map>
#define lli long long int
using namespace std;
vector <lli> G[100001];
int V[100001];	
int M[100001];
bool T[100001];
map <lli,lli> A;



lli GCD(lli a , lli b){
    if(b == 0)
        return a;
    else
        return GCD(b,a%b);
}
void DFS(lli i, lli gcdTillNow)
{
	if(T[i]==false)
	{	
		
		T[i]=true;
		gcdTillNow=GCD(gcdTillNow,V[i]);

		if(G[i].size()==1)// ie of leaf node
		{
			A[i]=M[i]-GCD(M[i],gcdTillNow);
		}
		else	// if not leaf node
		{
			for(lli j=0;j<G[i].size();j++)
			{
				DFS(G[i][j],gcdTillNow);
			}
		}	
	}

}
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		for(lli i=0;i<100001;i++)
			{
				G[i].clear();
			 	T[i]=false;
			 	V[i]=0;
				M[i]=0;	
			}
		A.clear();

		lli N;
		cin>>N;
		for(lli i=0;i<N-1;i++)
		{
			lli a,b;
			cin>>a>>b;
			G[a].push_back(b);
			G[b].push_back(a);
		}
		for(lli i=1;i<=N;i++)
			cin>>V[i];
		for(lli i=1;i<=N;i++)
			cin>>M[i];
		DFS(1,V[1]);

		// printing ANS

		map<lli,lli>::iterator it;
		for(it=A.begin();it!=A.end();it++)
		{
			cout<<it->second<<" ";
		}
		cout<<endl;

	}
 return 0;	
}

#35

He is missing your corner thoughts. As for me, I have been barely keeping up college work and related things these days.

@vijju123 Legends are not forgotten.


#36

But if only my corner is being missed then that means I can extend my break :stuck_out_tongue: . I will be back when my explanations get missed as well hehehehe :stuck_out_tongue:


#37

Look whose saying! :pray: :pray: :pray: :pray: :pray:


#38

@vijju123 Sir,we are missing you badly. Our life is hollow without your editorials and chef vijju’s corner :frowning: :frowning:


#39

Can someone please help me find my mistake in this??
https://www.codechef.com/viewsolution/24022307


#40

@ melfice please help me, what is the bug in my program, it run perfectly in my computer but didn’t get AC https://www.codechef.com/viewsolution/24027788 this is the link i have use dictionary for storing tree as well as result


#41

For all those who are getting TLE, try using fast input output. TLE arises because of the fact that computing gcd is a time consuming process.


#42

how you are getting this formula ml-gcd(g,ml) ??


#43

Better than the editorial


#44

For those getting TLE with DFS (in c++) use
ios_base::sync_with_stdio(false);
cin.tie(0);

SJ1 and SUBREM had pretty bad constraints. The above two lines should never be necessary for getting AC.
Here is a post regarding the rant