 Practice

Contest

SIMPLE

# Pre-requisites:

Dynamic Programming

# Problem:

Given a sequences of N positive numbers A, A, …, A[N-1], find how many subsequences of the integers are possible, for which the following procedure terminates in all integers equal to 1. The procedure is to take two unequal numbers, and replace the larger with the difference of the two. The procedure ends when all numbers become equal.

# Explanation:

Given a particular sequence of integers, the final number you end up with is the GCD of the numbers. This is because, at each step, the GCD remains invariant, and when all numbers are equal, their GCD will be the number itself.

The question then reduces to finding the number of subsequences of the sequence A, whose gcd is 1.

For this, we go through the numbers A, A, …, in order, and at each step make a choice as to whether to pick it, or not. We then have to also ask if at the end, the GCD will be 1, and so we recursively pass on the information of our current gcd.

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.

Finally, the answer we require is sum(pos = 0 to N-1) f(pos+1, A[pos]).

The above procedure needs to be memoized in order to work in time. Since A[i] <= 10^4, we get that current_gcd <= 10^4. In particular, the current_gcd will be a divisor of some A[i], hence the total number of states will be atmost N * (total number of divisors of A[i]). This is small enough to work in time, (certainly less than N * 10^4 per testcase).

# Setter’s Solution:

Can be found here

# Tester’s Solution:

Can be found here

21 Likes

you need to clear ur cache…it worked for me!!!

Hats Off to the problem setter…one of the best problem i have come across for a COOK-OFF…Keep it Up!.. 6 Likes

cant i use any approach other than DP?
I found out no of prime numbers and then found the no of subsets containing these prime number with some combinations!!
can somebody tell me whats wrong in this approach!
here is my code [link text]
: http://www.codechef.com/viewsolution/2172029

1 Like

I’m using the same … worked for me!!

Thats wrong, you have to find relatively prime numbers and NOT prime numbers. `finding the number of subsequences of the sequence A, whose gcd is 1.`

Hold on. Updating.

can’t open it yet =P

Maybe you’re looking for smth like this:

One can compute the complement of the requested number (the # of sequences with gcd > 1) using inclusion-exclusion principle: first add the # of all sequences such that their gcd is divisible by pi (where pi is prime), then subtract the # of all sequences such that their gcd is divisible by pi * pj (where pi, pj are prime), then add the # of all sequences such that their gcd is divisible by pi * pj * pk (where pi, pj, pk are prime) etc.
Each individual term can be computed very easily, one just has to find the number of elements in the sequence divisible by pi or pi * pj or p_i * p_j * p_k etc

1 Like

pi and pj are prime? OR pi and pj are prime to each other?

Respected Sir,
I am unable to understand the recurrence relation you have mentioned , can you explain the same a little more
Thanks

7 Likes

I did that and it passed. Here’s the link to my code: http://www.codechef.com/viewsolution/2169597

Please report such things on comments or send us an email to feedback@codechef.com. The answers on Editorials should be used for posting problem related content.

1 Like

pi and pj are both prime. The idea behind inclusion-exclusion is that once you determine the number of sequences such that their gcd is divisible by 2 and the same for divisible by 3, one double counts the ones such that the gcd is divisble by 6; hence, the need for subtraction.

3 Likes

The formula simply says: “I’m at position `pos` and actual gcd is `g`, then I have two possibilities 1.) to select the element at that position or 2.) skip that element.”

In formulas that is

1. select the element, actual gcd changes from g to gcd(g, actual element)
2. if you skip the element gcd is not changed

for such reccurence you need stop condition and it is “when I’m at position N” and there are also two possibilities, if actual gcd is 1, it is ok (return 1), else return 0.

18 Likes

What does submission status “??” mean?
I submitted the same code twice, one got AC and other was “??” which had a similar mark as WA in my submissions page.
Here are those:
AC: http://www.codechef.com/viewsolution/2172327
??: http://www.codechef.com/viewsolution/2172318

I could not figure out a reason for TLE verdict (link to my code).
The approach is same as the tester’s.

Any help would be appreciated.

1 Like

I’m just curious, the condition “All Ai will be distinct.” in problem statement is there for some reason?

1 Like

I can’t understand these two lines :

f(pos, 1) = 2^(N-pos) to speed up calculation.

Finally, the answer we require is sum(pos = 0 to N-1) f(pos+1, A[pos]).

Please explain. 1 Like

In Tester Solutions stl has been used. Why?

//