Problem Link:- SJ1 Problem - CodeChef
Solution:- By using simple BFS/DFS we can get the whole path from root to leaf of the tree.
Check this link:-Breadth First Search - Algorithms for Competitive Programming
(for in-depth info)
Now, the problem reduces to:-
"Given a sequence of integers, a1,a2…an , multiply each of them with k1,k2,…kn(non-negative integers of your choice), sum them up, then do modulo ‘m’ and the answer should be maximum
Equation looks like this:-
a1*k1+a2*k2+.......an*kn= D ;
Now, according to number theory, D is always divisible by gcd(a1,a2,…an).
Proof:- Linear Diophantine Equations - GeeksforGeeks
Let x=GCD(a1,a2,…an).
Therefore,
D=x*n;
where ‘n’ is some integer
So, no matter what values of k1,k2,k3,…kn, we choose, ‘D’ is always equal to ‘x*n’; where ‘x’ is fixed.
Problem reduces to :- find the maximum value of (x*n)%m;
where 'x' and 'm' are fixed . All we can do is choose a value of 'n' such that the above expression is maximized
‘n’ can be ‘1’,‘2’,‘3’,‘4’…whatever!
Now, comes the biggest doubt of the century, how can you say that ‘n’ can be anything?
Example:- 4,6 ; m=3;
Now, x=gcd(4,6)=2;
Therefore, D=2*n;
Now,
(2*n)%3 is maximum when ‘n’ is ‘1’ , but…but… ‘n’ can never be ‘1’ We cannot
obtain ‘2’ from the sequence:- ‘4’ , ‘6’ …so what !!! We get the same answer if n=1
or n=10; let n=10;
Therefore, 20%3=2 and also, 2%3=2; 20 can be achieved like this :-
4*5 + 6*0 =20
Hence, proved that ‘n’ can be anything we want from [1,infinity)
[In short, we can use k1,k2,k3,k4…kn to manipulate our sequence to get any value of ‘n’)
Problem reduces to finding that freaking ‘n’!
Now, we will use the knowledge of patterns, if you want to improve this skill, practice problems from January Long Challenge
-
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 we are 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.(Credits:- @yuv_sust)
Happy Coding!