Unofficial Editorial of SJ1

gcd

#1

Problem Link:- https://www.codechef.com/problems/SJ1

Solution:- By using simple BFS/DFS we can get the whole path from root to leaf of the tree.

Check this link:-https://cp-algorithms.com/graph/breadth-first-search.html
(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 :slight_smile:

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:- https://www.geeksforgeeks.org/linear-diophantine-equations/

Let x=GCD(a1,a2,…an).

Therefore,

       D=x*n;

where ‘n’ is some integer :slight_smile:
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’ :frowning: 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) :stuck_out_tongue:
[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’! :slight_smile:

Now, we will use the knowledge of patterns, if you want to improve this skill, practice problems from January Long Challenge :slight_smile:

  1. 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) :slight_smile:

Happy Coding!:slight_smile:


#2

Thank you very much for this post


#3

I knew it was not properly explained it in official editorial, so I explained it in as much detail as possible so even a 7th grader can understand :slight_smile: Happy coding bro!:slight_smile:


#4

Much better than official editorial


#5

Thanks a lot @karangreat234 for this wonderful explanation.


#6

Welcome!!! :slight_smile:


#7

@karangreat234 Again I have the same problem here as with other explanations how can we prove that for the answer we are getting using the formula m-GCD_{ans} we will always get non-negative coefficients satisfying a_1*k_1+a_2*k_2+.......a_n*k_n= D
you have just mentioned that n can be anything we want, but how can we prove for that n the coefficients will be non-negative ?

Then again I agree with this, but how can we definitely say the coefficients will be non-negative?


#8

I understood your explanation. But, I just tried to implement it in a different way but I am not getting where I am going wrong!

So, when we divide any integer a by b, we get an integer in the range [0, b - 1] as remainder. So, the maximum remainder that can be obtained on dividing by m is,
m - 1, if m - 1 is divisible by the GCD(a1, a2, a3,…an)
or, m - 2, if m - 2 is divisible by the GCD(a1, a2, a3,…an)
or…
or, 0, as the last option.

What is wrong with this logic?


#9

You will get TLE if m is of the order of 10^18,first you will check for m-1,then,m-2,then m-3…till m-m…and…so…on…