Help for problem

general
1

Can any one explain the recursion in Editorial? and what does function f(pos,current_gcd) does?

Really it is explained in tough manner please help

link http://discuss.codechef.com/questions/10495/amsgame2-editorial

2

I don’t know how to explain Visually here, otherwise I would have done that.
Nevertheless, I will try to explain it textually…

As you have said, you didn’t get the recursion part. So I think you are talking about this:

Thus, we can define the function:

f(pos, current_gcd) = f(pos+1, current_gcd) + f(pos+1,gcd(current_gcd, A[pos]))

with the base cases as
f(N, 1) = 1, f(N, k) =0 for k > 1,
f(pos, 1) = 2^(N-pos) to speed up calculation.

Here,

pos is variable which stores the index of element of array which is under consideration.

current_gcd is the variable which stores GCD of all no.s taken into the subsequence.

I think you must be fine till now.

Now, at this situation, you have 2 choices about taking the element at pos index into your subsequence:

  1. Ignore the element at this index in current subsequence.

    So what will happen in this case??

    i) The GCD of all element which are considered in the subsequence till now will remain same.

    ii) Now you have to take decision about element at pos+1 index.

    Hence, f(pos+1, current_gcd) this part is there.

  2. Take the element at this index in current subsequence.

    So what will happen in this case??

    i) The GCD of all element which are considered in the subsequence till now will change and get replaced by GCD of this element with current_gcd.

    ii) Now you have to take decision about element at pos+1 index.

    Hence, f(pos+1,gcd(current_gcd, A[pos])) this part is there.