AMSGAME2 - Editorial

Problem Link:

Practice

Contest

Difficulty:

SIMPLE

Pre-requisites:

Dynamic Programming

Problem:

Given a sequences of N positive numbers A[0], A[1], …, 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[0], A[1], …, 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

23 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][1]
[1]: CodeChef: Practical coding for everyone
thanx in advance!!

1 Like

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

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

9 Likes

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

6 Likes

#include <math.h>
#include <stdio.h>
typedef long long int LL;
int arr[100];

int gcd(int a, int b)
{
if(a<b)
{
	int tmp=a;
	a=b;
	b=tmp;
}

if(a%b==0)
	return b;
	
int c;
while(a%b!=0)
{
	c = b;
	b = a%b;
	a = c;
}
return b;
}
		
int main()
{
int t;
int n;
scanf("%d", &t);
int i,j;
int c;
int rgcd;
while(t--)
{
	scanf("%d", &n);
	for(i=0; i<n; i++)
	{
		scanf("%d", &arr[i]);
	}
	
	LL ans = 0;
	for(i=0; i<n; i++)
	{
		c = 0;
		for(j=i+1; j<n; j++)
		{
			if(gcd(arr[i], arr[j])==1)
				c++;
		}
		
		ans += ((pow(2.0, c)-1)*pow(2.0, n-i-c-1));
		
		if(arr[i]==1)
			ans++;
	}
	if(ans==0)
	{
		//if you didn't find any seq. yet.. check the whole sequence..
		rgcd = arr[0];
		for(i=1; i<n && rgcd!=1; i++)	
			rgcd = gcd(arr[i], rgcd);
		if(rgcd==1)
			ans++;
	}						
	printf("%lld\n", ans);
}
return 0;
}	

Can anybody tell me whats wrong with this code? I have counted all the numbers whose gcd is 1 w.r.t the current one, and all those which doesn’t have gcd as ‘1’. Then i calculated the sequences using the relation in the program…

@pragrame can you please explain how you came up with this dp function. Please elaborate it.
And also put some light on the condition to make it fast that you had mentioned in the last

1 Like

My approach: for each divisor, count the number of integers it divides (div[i]), then compute the numbers of sequences with GCD equal to i: A[i] == 2^(div[i])-1-sum(j from 2 to a_max)A[j*i]. The first term is the number of non-empty sequences with gcd divisible by i, the 2nd is subtracting all sequences with gcd equal to greater multiples of i.

Works in O(N*sqrt(a_max)+a_max*ln(a_max)) per test case, 0.04 s realtime.

4 Likes

@bugkiller , went through your solution . nice approach used. can you elaborate the process ?

4 Likes

My approach :

I calculated gcd of all elements of power set of the numbers. Counted number of GCDs which were 1. Still it gave wrong answer. It was working on sample testcase. Can anyone point out what was wrong? Code is here : CodeChef: Practical coding for everyone

This may give TLE but I am more worried about the wrong answer(WA) right now.

can someone explain me why we have to add up (pos 0 to n-1 ), won’t the recursive function
f ( 0,a[0] ) count all the conditions as it includes, including and exculding every element?

The answer when only two elements are present i.e. 1 and 2 should be 1 but your recurrence relation is giving the answer as 2 i.e. it is counting two subsets having gcd=1 -> {1} and {1,2} while {1} cannot be considered valid. Can u explain??

one more question, the time taken per testcase is N * 10^4 and there are 100 test cases at most. In the worst case scenario, N would be 60 so time taken would be 60 * 10^4 * 100 or 6*10^7. I dont think this could run in 1 sec time limit…

CodeChef: Practical coding for everyone. Can any body plz tell me wats wrong on this?

http://www.codechef.com/viewsolution/2174587

My above code is AC. But when I uncomment the commented line it gives WA. Basically, commented line is implementation of

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

I’m unable to understand why this is happening. Can anyone please explain ?

Could anyone explain what the recursive function is actually doing ??

how are we making subsets here then ??

I didnt understand the recurrence part…
plz elaborate with an example…
anyone?

1 Like

I didnt understand the recurrence part…
plz elaborate with an example…
anyone?