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.
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
2 Likes
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 COOK-OFF…Keep it Up!..
7 Likes
I’m using the same … worked for me!!
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.
Hold on. Updating.
can’t open it yet =P
pi and pj are prime? OR pi and pj are prime to each other?
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.
1 Like
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.
3 Likes
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.
21 Likes
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: CodeChef: Practical coding for everyone
??: CodeChef: Practical coding for everyone
In Tester Solutions stl has been used. Why?
@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?
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…
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”.
4 Likes
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.
@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.
3 Likes