Unofficial Editorial of SJ1

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 :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:- Linear Diophantine Equations - GeeksforGeeks

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:

16 Likes

Thank you very much for this post

1 Like

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:

1 Like

Much better than official editorial

3 Likes

Thanks a lot @anon55659401 for this wonderful explanation.

1 Like

Welcome!!! :slight_smile:

@anon55659401 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?

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?

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…

Thanks for the explanation. I understood till the point where you mentioned that n can be anything [1,infinity]. But how did you arrive at the conclusion that the answer will be m - gcd(G,m) ?

As per your explanation, you made an observation that it starts repeating at 6 with a gap of 3 but i don’t get it how you related the value 3 to gcd of 21 and 15 ? Is it some concept that I’m missing here or we got the relation by trial and error.

Its pure observation + I’ve done tons of problems like these, so the observation part came naturally to me :slight_smile: