×

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

This question is marked "community wiki".

973568379
accept rate: 14%

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

(20 May '13, 00:18) 4★
6

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

(20 May '13, 00:19)

I'm using the same .. worked for me!!

(20 May '13, 00:21)

Hold on. Updating.

(20 May '13, 00:24) 0★

can't open it yet =P

(20 May '13, 00:24) 3★
1

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.

(20 May '13, 00:35) 0★

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

(20 May '13, 00:52)
showing 5 of 7 show all

 7 Respected Sir, I am unable to understand the recurrence relation you have mentioned , can you explain the same a little more Thanks answered 20 May '13, 00:30 2★rpf1123 102●1●2 accept rate: 0% 18 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 select the element, actual gcd changes from g to gcd(g, actual element) 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. (20 May '13, 00:47)
 4 @bugkiller , went through your solution . nice approach used. can you elaborate the process ? answered 20 May '13, 21:44 2★al3x1784 0●4●14●16 accept rate: 0% @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) al3x17842★ 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) al3x17842★ 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) paramvi3★ @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) nil962★ showing 5 of 8 show all
 1 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 425●3●7●17 accept rate: 4% 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. (20 May '13, 00:24)
 1 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 answered 20 May '13, 00:27 6★tibip 136●1●1●5 accept rate: 0% 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) lg52937★ 3 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. (20 May '13, 00:36) tibip6★
 1 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 2★svm11 429●3●7●9 accept rate: 12% 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)
 1 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 16.8k●49●115●225 accept rate: 11% In Tester Solutions stl 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 sub-sequences will be unique. Otherwise, there would have been many doubts regarding whether to count only unique sub-sequences 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 sub-sequences or not." the problem would be slightly harder to understand, but the algorihm is correct if there are duplicities or not ;-) Of cource two sub-sequences are different iff element indexes from original sequence are different. (20 May '13, 13:51) @bugkiller: That was the reason I asked why 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
 1 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. :) answered 20 May '13, 01:45 56●1●4●12 accept rate: 0% 4 once actual gcd is 1, it cannot change to something else... ...and when you are at position pos, there are (N-pos) elements in sequence and you can use every possible subset of those (N-pos) elements. Number of subsekt for K elements is 2^K. That meaning of the sum is "choose element at position i as first one". (20 May '13, 03:11)
 1 @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 11 accept rate: 0% 1 I described it better in this thread - http://discuss.codechef.com/questions/10495/amsgame2-editorial?page=1#10531 Something unclear? (20 May '13, 13:48)
 1 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. answered 20 May '13, 21:23 7★xellos0 5.8k●5●40●88 accept rate: 10% 16.8k●49●115●225
 0 #include #include typedef long long int LL; int arr[100]; int gcd(int a, int b) { if(a
 0 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 2★akshat91 1 accept rate: 0% counter example is 1 1 1  your code prints 0 - http://ideone.com/OF9ewE, { 1 } is correct sub-sequence (21 May '13, 02:16)
 0 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? answered 21 May '13, 00:35 4★srinu634 76●1●4●9 accept rate: 0% You have to choose the first element somehow, in f(0, a[0]) you chose a[0] as GCD, but if you skip a[0] GCD is different... (21 May '13, 02:11)
 0 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 30●3 accept rate: 0%
 0 http://www.codechef.com/viewsolution/2174396. Can any body plz tell me wats wrong on this? answered 21 May '13, 14:17 21●1●3●9 accept rate: 0%
 0 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 ? answered 21 May '13, 17:41 2★rjdhania 26●1 accept rate: 50%
 0 Could anyone explain what the recursive function is actually doing ?? answered 21 May '13, 18:44 1 accept rate: 0% The recursive function is calling itself recursively. :D Read this http://discuss.codechef.com/questions/10495/amsgame2-editorial?page=1#10531 (21 May '13, 18:46)
 0 how are we making subsets here then ?? answered 21 May '13, 19:05 1 accept rate: 0%
 0 I didnt understand the recurrence part.... plz elaborate with an example.... anyone? answered 20 Aug '13, 23:39 0●1●3 accept rate: 0%
 0 I didnt understand the recurrence part.... plz elaborate with an example.... anyone? answered 20 Aug '13, 23:40 0●1●3 accept rate: 0%
 0 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. please explain what are these lines doing. answered 25 Oct '13, 04:46 1 accept rate: 0%
 0 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 4★pawan55 0●2 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×13,777
×1,523
×950
×10
×9

question asked: 20 May '13, 00:07

question was seen: 11,207 times

last updated: 25 Sep '14, 20:02