Problem Link:Difficulty:SIMPLE Prerequisites:Dynamic Programming Problem:Given a sequences of N positive numbers A[0], A[1], ..., A[N1], 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: Finally, the answer we require is sum(pos = 0 to N1) 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
This question is marked "community wiki".
asked 20 May '13, 00:07
showing 5 of 7
show all

@bugkiller , went through your solution . nice approach used. can you elaborate the process ? answered 20 May '13, 21:44
@al3x1784 >> Actually its not my solution, its acube's solution. See the comment on the top of the code. And you'll understand it if you start by taking an example (2, 3); then extend it to (2, 3, 4). Comment back your progress whether you got it or not, then I will help you. :)
(20 May '13, 23:07)
Thanx for replying btw if you have understood well then pls explain giving the link to the solution so that everybody will get benefitted. :)
(20 May '13, 23:12)
1
For example, lets start with the array {2, 3}. in the for loop, it does nothing and comes out and sets d[2] = 1, okay? then for 3, it went into the if clause, and updates d[gcd(2,3)] = d[1] to 1. Finally we are printing d[1] which was 1. Pretty fair? Now similarly we will proceed for array {2, 3, 4}
(20 May '13, 23:14)
Fine then here you go http://www.codechef.com/viewsolution/2172327
(20 May '13, 23:17)
explain this part...
for (; n;) {
int x;
scanf("%d", &x);
for (int i = 1; i <= 10000; i++)
if (d[i])
d[__gcd(i, x)] += d[i]; //here?
d[x] += d[0]; // why this?
}
(20 May '13, 23:17)
1
because, if no such d[i] was found then you know that this element was encountered previously so you update it so that elements coming in future know that particular d[i] is not zero anymore. Told you, take an example and you'll be fine with it.
(20 May '13, 23:28)
Thanks @bugkiller and acube for such a wonderful algorithm to such a nice problem. Learnt so much.
(23 May '13, 05:16)
@bugkiller i can get the answer by dry run of ur code but cant get the logic of the line "d[__gcd(i, x)] += d[i];" please explain
(25 Sep '14, 20:02)
showing 5 of 8
show all

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 thanx in advance!! answered 20 May '13, 00:21
Thats wrong, you have to find relatively prime numbers and NOT prime numbers.
(20 May '13, 00:24)

Maybe you're looking for smth like this: One can compute the complement of the requested number (the # of sequences with gcd > 1) using inclusionexclusion 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 answered 20 May '13, 00:27
pi and pj are prime? OR pi and pj are prime to each other?
(20 May '13, 00:30)
I did that and it passed. Here's the link to my code: http://www.codechef.com/viewsolution/2169597
(20 May '13, 00:32)
3
pi and pj are both prime. The idea behind inclusionexclusion 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.
(20 May '13, 00:36)

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. answered 20 May '13, 01:15
How curious. It seems the addition of long in Java is unfathomably slow! Your solution passes well within the time limits with just this little change. Do a diff to figure.
(20 May '13, 22:00)

I'm just curious, the condition "All Ai will be distinct." in problem statement is there for some reason? answered 20 May '13, 01:41
In Tester Solutions stl <set> has been used. Why?
(20 May '13, 02:16)
@bit_cracker007 >> because gcd of {a, a, c} and {a, c} is the same so why keep duplicate elements in the array, hence set is used to keep only unique elements. But again as @betlista pointed out if all Ai are really distinct then why is tester using set?
(20 May '13, 02:58)
but, if the original sequence is {a, a, c}, than there are two sub sequence {a, c}, so you simply cannot keep only unique elements...
(20 May '13, 03:08)
3
@bit_cracker007 As a tester it is important to submit solutions that assert the bounds of the test data. The set exists to simply verify that the given numbers are unique. This way, as we keep changing the test files and rejudging our submissions we automatically verify that the the bounds of the input are met. "All Ai will be distinct" has a very important role. It means that all subsequences will be unique. Otherwise, there would have been many doubts regarding whether to count only unique subsequences or not. The problem would have been slightly harder in that case.
(20 May '13, 11:28)
@gamabunta thanks for your answer, I agree with you: "Otherwise, there would have been many doubts regarding whether to count only unique subsequences or not." the problem would be slightly harder to understand, but the algorihm is correct if there are duplicities or not ;) Of cource two subsequences are different iff element indexes from original sequence are different.
(20 May '13, 13:51)
@bugkiller: That was the reason I asked why <set> has been used when all a[i] are already distinct. :) @gamabunta : Thanks for clarifying.
(20 May '13, 20:51)
showing 5 of 6
show all

@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 answered 20 May '13, 13:41
1
I described it better in this thread  http://discuss.codechef.com/questions/10495/amsgame2editorial?page=1#10531 Something unclear?
(20 May '13, 13:48)

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])1sum(j from 2 to a_max)A[j*i]. The first term is the number of nonempty 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. answered 20 May '13, 21:23

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 : http://www.codechef.com/viewsolution/2170999 This may give TLE but I am more worried about the wrong answer(WA) right now. answered 20 May '13, 22:07
counter example is
your code prints 0  http://ideone.com/OF9ewE, { 1 } is correct subsequence
(21 May '13, 02:16)

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.. answered 21 May '13, 09:24

http://www.codechef.com/viewsolution/2174396. Can any body plz tell me wats wrong on this? answered 21 May '13, 14:17

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 I'm unable to understand why this is happening. Can anyone please explain ? answered 21 May '13, 17:41

Could anyone explain what the recursive function is actually doing ?? answered 21 May '13, 18:44
The recursive function is calling itself recursively. :D Read this http://discuss.codechef.com/questions/10495/amsgame2editorial?page=1#10531
(21 May '13, 18:46)

I didnt understand the recurrence part.... plz elaborate with an example.... anyone? answered 20 Aug '13, 23:39

I didnt understand the recurrence part.... plz elaborate with an example.... anyone? answered 20 Aug '13, 23:40

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^(Npos) to speed up calculation. please explain what are these lines doing. answered 25 Oct '13, 04:46

why does a normal bottom up approach using tabular method gives TLE..whereas top down memoized soln gives AC although complexity looks the same in both cases ie O(N10^4logN) in worst case: bottom up dp: http://www.codechef.com/viewsolution/3642604 top down memoized: http://www.codechef.com/viewsolution/3643384 answered 24 Mar '14, 22:12

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 COOKOFF..Keep it Up!...:D
I'm using the same .. worked for me!!
Hold on. Updating.
can't open it yet =P
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.
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