RECNDSUB - Editorial

editorial
, , , , , ,
2

can someone explain it more clearly the value of pi is equivalent to choosing (c1−i) items from the bag of c items?

2 Likes
3

Suppose you have
p=count of 1;
q=count of -1;
z=count of 0;

Suppose you want to make sum k>0 (for k<0 process is similar).
Let’s see the choices we have,
!st choice → take k 1’s and 0 -1’s number of ways to do this = pCk * qC0;
2nd choice → take k+1 1’s and 1 -1’s number of ways to do this = [ pC(k+1) ] * [qC1]
3rd choice → take k+2 1’s and 2 -1’s number of ways to do this = [ pC(k+2) ] * [qC2]

and so on.

This sum turns out to be (p+q)C(q+k) using binomial expansion of (1+x)^p and (1+1/x)^q

Also with all these choices you have the choice to take any number of zeros
therefore multiply power(2,z) in each term and take the sum modulo m;

For case of zero we can’t have empty subsequence so -1 for the case of zero.

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

8 Likes
4

@zacky_901 Could you please elaborate on this. Thanks!

5

Another (maybe more intuitive) way to derive the answer:

Let cnt_{-1}, cnt_{-0} and cnt_{1} represent the number of occurrences of -1, 0, and 1 respectively.

Now suppose you wish to calculate the number of ways to obtain a positive sum = k (similar approach can be used for a negative sum). Then the number of ways to do so would be to take k amount of 1's and then out of the remaining 1’s (i.e. cnt_{1} - k), for each 1 you take, you have to also take a -1 (so that the sum remains k). Also, we can add in extra 0's since they do not effect the sum.

This can be expressed as:

ways[k] = 2^{cnt_{-0}} * \sum_{i=0} \binom{cnt_{1}}{k + i} *\binom{cnt_{-1}}{i}

\quad \quad \quad \space \space \space= 2^{cnt_{-0}} * \sum_{i=0} \binom{cnt_{1}}{cnt_{1} - k - i} *\binom{cnt_{-1}}{i}

Now, we can use Vandermonde’s identity to get:

ways[k] = 2^{cnt_{-0}} * \binom{cnt_{1} + cnt_{-1}}{cnt_{1} - k}

35 Likes
6

Thanks bro. That helped. Wasn’t aware of this identity. Had come up with summation expression but wasn’t able to simplify it. Are you aware of more questions which use this identity?

1 Like
7

I cannot recall any questions which use this identity but googling “codechef vandermonde’s identity” revealed that GMEDIAN’s editorial mentioned this identity.

2 Likes
9

Hey! I have a doubt. The limit of i in summation ranges from 0 to min(cnt1-k,cnt-1) if i am not wrong. So my question is wont it effect the identity? bcz in identity upper limit is necessarily needed to be cnt1-k

2 Likes
10

@m0nk3ydluffy Just for curiosity, what came to your mind before applying nCr = nCn-r identity, cause I was stuck on that step and I wanted a closed-form of summation but I was not able to get it. Maybe because I had never used Vandermonde’s Identity before, but after reading Wikipedia article I feel this identity is very intuitive especially after reading combinatorial proof in the given article. So what are your thoughts, what should we do in such cases?

11

Value of nCr is zero when r<0 or r>n. This fact preserves the mathematical soundness of all combinatorial identities. So you could very well change the range of i in that summation, it won’t make the identity incorrect :slight_smile: .

3 Likes
12

Oh yeah i got that thanx!

13

Hey!. As @anon49376339 said, we generally define binomial coefficient \binom{n}{m} to be equal to zero if m is not in the valid range (valid range being 0 <= m <= n). So we do not have to care about the upper bound in the identity (hence I did not specify any upper bound in the summation). In fact, the identity would be valid even if we sum over all the integers in [-\infin, \infin] (as we have defined the binomial coefficient to be zero for negative m)

1 Like
14

Hey! I guess you mean “nCr = nC(n - r) identity”. You can read https://trans4mind.com/personal_development/mathematics/series/summingBinomialCoefficients.htm. It has some interesting tricks which might be helpful in the future.

2 Likes
15

Yeah! I got that thanx

16

If anyone was wondering about primitive roots for NTT, I found some to be 18 for 2^21, and 55 for 2^22

2 Likes
18

@m0nk3ydluffy Yes , my bad !

19

Can anybody tell me why I am getting WA
https://www.codechef.com/viewsolution/32375114
I have applied a same approach.

21

I used same approach as you but with modulo inverse. Can you tell me how to speed up the solution, my solution passed but took around 1 second. I stored factorials upto 1e5 and modinverse of factorials upto 1e5. I guess complexity of precomputation should be O(N\log(P)) where P is the prime, and complexity in finding answer will be O(N) still it takes 1000ms.

How should I improve complexity, I suppose the computation of moduloinverse is taking a lot of time.

Here is submission: CodeChef: Practical coding for everyone

22

You can precompute in O(n + \log(p))
If you understand modular arithmetic, why this works should be obvious.

vector<ll> fact;
vector<ll> invfact;
void computefactorial(int n){
    fact.resize(n);
    invfact.resize(n);
    fact[0]=1;
    for(int i=1;i<n;i++){
        fact[i]=i*fact[i-1];
        fact[i]%=p;
    }
    invfact[n-1]=modpower(fact[n-1],p-2);
    for(int i=n-2;i>=0;i--){
        invfact[i]=(i+1)*invfact[i+1];
        invfact[i]%=p;
    }
}
1 Like
23

Multiply those polynomials and write down the coefficient of x^K in the product,
[(1+x)^(p+q)]/[x^q].
This coefficient will be the same as the summation of terms above.

24

Oh my god how I missed this, going in reverse! So we only need one call to binary_exp. Thanks for eye opener

Now I am getting 320ms, much improved than 1000ms earlier.