COUNTREL - Editorial

PROBLEM LINKS

Practice
Contest

DIFFICULTY

EASY

EXPLANATION

Part 1 closed form: (3^n+1)/2 - 2^n

Part 2 closed form: 2*4^(n-1) - 3^n + 2^(n-1) + 2^n - (3^n+1)/2

The answer (for both 1 and 2) is in the form of a * 4^n + b * 3^n + c * 2^n + d for some small constants a,b,c,d.

You can calculate 4^n%MOD, 3^n%MOD, 2^n%MOD in log(n) time using fast exponentiation for an overall complexity of O(log(n)).

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.

2 Likes

anyone pls explain how the closed form arrived

@shesh_neo : You have to form a recurrence relation and solve it and apply initial conditions to get to the closed form . Let me know if you have trouble forming a recurrence relation , I will post the relation .

1 Like

for the part 1:
let’s say we have f(n) for n, so we can easily deduce, f(n+1)=f(n)*3+2^n-1
so, f(n+1)+2^(n+1)-1/2=(f(n)+2^n-1/2)*3
let’s say k(n)=f(n)+2^n-1/2
so k(1)=3/2, k(n+1)=k(n)*3, so k(n)=3^n/2
so, f(n)=3^n/2-2^n+1/2

http://artofproblemsolving.com/community/c2340h1259828_number_of_subset_pairs

To all the people trying this question, here’s a special note:
Don’t calculate like, a=4^n%MOD, b= 2^n%MOD and c=3^n%MOD, and then do 2*a + b/2 + b + ((c+1)/2), and similar things for R1… This will give you a wrong answer…because what we actually want to find is like : ((3^n + 1)/2)%MOD, which is Actually : (3^n + 1)%MOD * (2^MOD-2)%MOD… So don’t forget to leave the divider alone, take that into consideration too…I did this mistake many a times before realizing it !
Cheers ! :smiley:

I get a different closed form, maybe we have some different detail :slight_smile:
mine is

\frac{-3 * 3^n + 4^n - 1}{2} + 3 * 2^{n - 1}

https://www.codechef.com/viewsolution/19967388

please post the recursive relation and how to come up with the formula.

2 Likes

@sparshgunner12 : check my solution for the recursive relation and the explanation about how to come up with the formula. Everything is mentioned in the comments.

1 Like

@shesh_neo : check my solution for the recursive relation and the explanation about how to come up with the formula. Everything is mentioned in the comments.