SJ1 - Editorial

PROBLEM LINK:

Practice
Contest, div. 1
Contest, div. 2

Author: Sumit Jain
Tester: Zhong Ziqian
Editorialist: Oleksandr Kulkov

DIFFICULTY:
EASY
PREREQUISITES:
Euclid’s algo, DFS
PROBLEM:
You’re given rooted tree with N nodes. Each node has value v_i and parameter m_i. Let denote leafs of the tree as l_1,\dots,l_L in icreasing order. For each leaf l_i you have to find answer a_i which is defined as maximum possible remainder modulo m_{l_i} of some integer linear combination of values of the vertices on the path from l_i to the root.
QUICK EXPLANATION:
For each leaf you should output m_{l_i}-\gcd(g,m_{l_i}) where g is \gcd of all values on the path from the leaf to the root.
EXPLANATION:
Since we consider only integer linear combinations, we may prove that arbitrary number x may be obtained as linear combination of v_1, \dots, v_k if and only if it’s divisible by g=\gcd(v_1,\dots,v_k).

It’s proven by induction: for k=2 it’s true because any linear combination is divisible by g and we always may find linear combination which is equal to g by extended Euclid’s algorithm. This means that if we consider triple (v_1,v_2,v_3) we may actually substitute pair (v_1,v_2) by single number which is equal to \gcd(v_1,v_2), then we substitute (\gcd(v_1,v_2),v_3) with single number \gcd(v_1,v_2,v_3) for the same reason. In this manner it may be proven for arbitrary k.

Now if we consider single number g (which is equal to \gcd of all values on the path to the root) what’s the largest remainder modulo m we can obtain among numbers g, 2g, 3g, \dots? All of these numbers are divisible by g'=\gcd(g,m). Moreover, one of them is equal to g'! Indeed, let’s look on diophantine equation k_1g=g'+k_2m. Since both g and m are divisible by g', we may reduce the whole equation by it so we will have k_1\tfrac{g}{g'}-k_2\tfrac{m}{g'}=1 and since \tfrac{g}{g'} and \tfrac{m}{g'} are co-prime, this equation will always have a solution. Thus we may substitute g with g' and after that we may immediately say what’s the largest remainder of kg' modulo m. Since m is divisible by g' the answer is simply m-g'.

Knowing that fact, we may solve the problem by simple depth-first search if we will calculate \gcd of all values from the root to the current node in it. This will solve the problem in O(N \log C):

void dfs(int v = 1, int p = 1, int G = val[1]) {
	for(auto u: g[v]) {
		if(u != p) {
			dfs(u, v, __gcd(G, val[u]));
		}
	}
	if(g[v].size() == 1 && v != 1) {
		ans[v] = mod[v] - __gcd(mod[v], G);
	}
}

AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
Editorialist’s solution can be found here.

12 Likes

Could someone help me debug this ? I’am not sure where I went wrong.
https://www.codechef.com/viewsolution/23988805

1 Like

Aree,you are using same graph for every testcase,you should use new graph for each testcase :slight_smile:

1 Like

I’m not completely sure what you’re saying, I tried clearing the graph (line 73 in the code).

can someone help me to debug this program? I am not getting what’s wrong with this [https://www.codechef.com/viewsolution/23994649]

I am also getting TLE with the similar approach.

You haven’t cleares v[n],vectors of vectors :slight_smile:

Can anyone help out why I am getting TLE?
https://www.codechef.com/viewsolution/24002064

Can anyone help me with this problem.
I’m getting WA on every testcase except the last (11th) one. I couldn’t think of any test case where my code would fail.
I’m doing exactly what is said in the editorial.
Here is the link to my code: https://pastebin.com/NVf2ARCH
Thank you.

" Since m is divisible by g′ the answer is simply m−g′ ". Please explain this statement.

@shivamgor498 because m-g’ is the greatest remainder you can get. Consider m = 8 and g’ = 2, now what is the greatest remainder you can get for the equation g’*x % m. Clearly it is 6 for our example.

2 Likes

Since its undirected graph edge u and v can be in any order so you need to do tree[y].push_back(x) as well.

1 Like

Hey man I just go through your code and did some modification.

You can find here Link

Ask if you have any issue.

and try to use ios::sync_with_stdio(false) in your main function if you are using cin and cout.

It will make your code much faster sometimes like this time it cost TLE if you’ll not use that because inputs are huge

1 Like

Yes, thank you. That helped.

I got TLE first with a similar DFS approach then I tried the problem with BFS and got AC. But I am still not sure why DFS solution got TLE with 10^5 constraints?

Good Tutorial. But,
There are two things that might make things easier:

  1. Diophantine Equations property. That is,
    Ax + By + Cz + … = D
    This is called Diophantine Equation and If you sum up all the
    node value as what the problem said you will get this type of
    equation where constant A, B, C, … are node value and x, y, z… is unknown the value you are said to multiply.
    This equation can be solved with Extended Euclid Algo. But don’t worry we do not need to solve this. All we need is to understand it’s one property that,
    this equation has no integral solutions if ‘D’ is not a multiple of
    GCD (A, B, C, … ) (For proof please google it).
    Let the GCD of all node value is G. So, here D = n * G.
    So all we need is to find the maximum value of ( (n*G) % m )

  2. Now let’s make an observation:
    Let say, G = 21, m = 15. and n = 1, 2, 3, 4…
    ( 1 * 21 ) % 15 = 6
    ( 2 * 21 ) % 15 = 12
    ( 3 * 21 ) % 15 = 3
    ( 4 * 21 ) % 15 = 9
    ( 5 * 21 ) % 15 = 0
    ( 6 * 21 ) % 15 = 6 and repeat…
    So, take a look. Here I am getting mod value from 0 to 12 with an
    interval of 3. Where does this 3 come from. Magically this 3 is the
    GCD of 21 and 15. Let’s give it a name “GCD_ans”.

Decision: So, the answer for a single Leaf = m - Gcd_ans
Here, ans = 15 - 3 = 12

I hope this will help to understand the solution.

61 Likes

can someone help me find the problem in this?
https://www.codechef.com/viewsolution/23996706

this is better explanation.

Superb explanation. Thanks.

I am not saying that this is badly written but still after reading it, I am missing @taran_1407 and @vijju123 's editorials. Thanks for the quick editorial though.

4 Likes