SJ1 - Editorial

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:

1 Like

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

2 Likes

@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 "

3 Likes

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

now i am able to understand it clearly,thanks man

@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 "

1 Like

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;	
}

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.

3 Likes

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:

1 Like

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

2 Likes

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

1 Like

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

@ melfice please help me, what is the bug in my program, it run perfectly in my computer but didn’t get AC CodeChef: Practical coding for everyone this is the link i have use dictionary for storing tree as well as result

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.

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

Better than the editorial

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

2 Likes

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.

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.

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?