You are not logged in. Please login at www.codechef.com to post your questions!

×

AMSGAME2 - Editorial

21
10

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

This question is marked "community wiki".

asked 20 May '13, 00:07

pragrame's gravatar image

6★pragrame ♦♦
963568379
accept rate: 14%

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

(20 May '13, 00:18) kunal3614★
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) rahul_nexus3★

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

(20 May '13, 00:21) prakharmy3★

Hold on. Updating.

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

can't open it yet =P

(20 May '13, 00:24) edufgf3★
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) admin ♦♦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) bugkiller3★
showing 5 of 7 show all

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

link

answered 20 May '13, 00:30

rpf1123's gravatar image

2★rpf1123
10212
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

  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.

(20 May '13, 00:47) betlista ♦♦3★

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

link

answered 20 May '13, 21:44

al3x1784's gravatar image

2★al3x1784
041416
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) bugkiller3★

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) bugkiller3★
(20 May '13, 23:17) bugkiller3★
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) bugkiller3★

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) nil963★
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!!

link

answered 20 May '13, 00:21

jaythegenius's gravatar image

3★jaythegenius
4253717
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) bugkiller3★

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

link

answered 20 May '13, 00:27

tibip's gravatar image

6★tibip
136115
accept rate: 0%

edited 20 May '13, 00:28

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

(20 May '13, 00:30) bugkiller3★

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★

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.

link

answered 20 May '13, 01:15

svm11's gravatar image

2★svm11
429379
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) gamabunta1★

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

link

answered 20 May '13, 01:41

betlista's gravatar image

3★betlista ♦♦
16.8k49115224
accept rate: 11%

edited 20 May '13, 01:42

In Tester Solutions stl <set> has been used. Why?

(20 May '13, 02:16) bit_cracker0073★

@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) bugkiller3★

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) betlista ♦♦3★
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) gamabunta1★

@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) betlista ♦♦3★

@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) bit_cracker0073★
showing 5 of 6 show all

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

link

answered 20 May '13, 01:45

amanjain110893's gravatar image

4★amanjain110893
561412
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) betlista ♦♦3★

@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

link

answered 20 May '13, 13:41

chetan98351's gravatar image

3★chetan98351
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) betlista ♦♦3★

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.

link

answered 20 May '13, 21:23

xellos0's gravatar image

7★xellos0
5.7k53981
accept rate: 10%

edited 21 May '13, 02:17

betlista's gravatar image

3★betlista ♦♦
16.8k49115224

#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...

link

answered 20 May '13, 07:29

nitish712's gravatar image

4★nitish712
102
accept rate: 0%

Initially i had also used similar approach but it counts only those sequences which have at least one pair with gcd=1. It doesn't count sub sequences such as (6,10,15) in which no pair is relatively prime.

(20 May '13, 10:01) vani15_213★

I also had done this before.This is wrong.You Dont need to do this.The number of gcds are small(10^4),so u can use idea of subset-sum problem in here.

(20 May '13, 12:18) coolbun3★

sry abt that.. i didnt think this way.. thanx alot.. :)

(20 May '13, 13:19) nitish7124★

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.

link

answered 20 May '13, 22:07

akshat91's gravatar image

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) betlista ♦♦3★

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?

link

answered 21 May '13, 00:35

srinu634's gravatar image

4★srinu634
76149
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) betlista ♦♦3★

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

link

answered 21 May '13, 09:24

red_coder's gravatar image

3★red_coder
303
accept rate: 0%

edited 21 May '13, 09:47

http://www.codechef.com/viewsolution/2174396. Can any body plz tell me wats wrong on this?

link

answered 21 May '13, 14:17

timepass123's gravatar image

2★timepass123
21139
accept rate: 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 ?

link

answered 21 May '13, 17:41

rjdhania's gravatar image

2★rjdhania
261
accept rate: 50%

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

link

answered 21 May '13, 18:44

bahlsahil's gravatar image

3★bahlsahil
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) bugkiller3★

how are we making subsets here then ??

link

answered 21 May '13, 19:05

bahlsahil's gravatar image

3★bahlsahil
1
accept rate: 0%

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

link

answered 20 Aug '13, 23:39

sidashsahil's gravatar image

1★sidashsahil
013
accept rate: 0%

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

link

answered 20 Aug '13, 23:40

sidashsahil's gravatar image

1★sidashsahil
013
accept rate: 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.

link

answered 25 Oct '13, 04:46

sudhanshu1994's gravatar image

2★sudhanshu1994
1
accept rate: 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

link

answered 24 Mar '14, 22:12

pawan55's gravatar image

4★pawan55
02
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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:

×11,590
×1,259
×780
×10
×9

question asked: 20 May '13, 00:07

question was seen: 10,320 times

last updated: 25 Sep '14, 20:02