AMSGAME2 - Editorial

editorial
, , , ,
41 
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?
	 	}

```
42

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.

1 Like
43

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?

44

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…

45

counter example is

1
1
1

your code prints 0 - http://ideone.com/OF9ewE, { 1 } is correct sub-sequence

46

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…

47

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

48

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 ?

49

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

50

The recursive function is calling itself recursively. :smiley:
Read this http://discuss.codechef.com/questions/10495/amsgame2-editorial?page=1#10531

51

how are we making subsets here then ??

52

Thanks @bugkiller and acube for such a wonderful algorithm to such a nice problem. Learnt so much.

53

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

54

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

55

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.

56

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

57

@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