PROBLEM LINK:Author and Editorialist: Lalit Kundu DIFFICULTY:mediumhard PREREQUISITES:combinatorics, fastfourier transform, divide and conquer PROBLEM:Given an array of integers $A_1, A_2, ..., A_N$ and an integer $K$, count number of ways to choose a multiset(i.e. a set with duplicate elements) of size $K$. Two multisets are different iff count of any element is different in both. QUICK EXPLANATION:====================== EXPLANATION:================ Theorem 1: Theorem 2: We'll avoid the proof here, but you can follow above link to explore more. Now, assume we have $k$ distinct elements in the array with frequencies $f_1, f_2, ..., f_k$. Let's say $x_i$ is the frequency of $i^{th}$ distinct element in chosen multiset, then $x_1 + x_2 + ... + x_k = K$, where $x_i \le f_i$. So, from above theorem, we need to find coefficient of $x^K$ in polynomial $\dfrac{(1  x^{f_1 + 1})*(1  x^{f_2 + 1})*....*(1  x^{f_k + 1})}{(1x)^{k}}$. Note we can evaulate the numerator since it's degree is $O(f_1 + f_2 + ..., f_k) = O(N)$. Let's say we use FFT to multiply two polynomials of degree $p$ in $O(p \text{ log } p)$. If we start multiplying these $k$ terms in numerator in the given order, it could still take $O(N^2)$ worst case. Here comes in the idea of divide and conquer. At each step we break down numerator into two parts with $k/2$ terms each, solve them recursively and multiply to find the polymial. This approach takes $O(N \text{log}^{2} N)$ worst case. For multiplication of two polymials you can use FTT or even Karatsuba. For further reading on these algorithms you can read this. AUTHOR'S, TESTER'S SOLUTIONS:asked 23 Oct '16, 23:57

Can you provide me with a link to a tutorial for Fast Fourier transform with implementation details? It would be of great help to start with... :) answered 24 Oct '16, 03:23
2
I used the code from here: https://www.hackerrank.com/challenges/emmaandsumofproducts/editorial
(25 Oct '16, 01:26)

I did Π(1+...+xi^fi) and got ac. Is there any advantage in doing Π (1−xi^(fi+1))/(1x) answered 24 Oct '16, 19:15
In what order do you take the polynomials? I thought of always multiplying the two polynomials with smallest degrees. But what is it's complexity? Is it n log^2n?
(24 Oct '16, 21:42)
I did the same too but had to multiply the polynomials in increasing order of degrees. This solution: https://www.codechef.com/viewsolution/11936211 uses the same fft code as mine but doesn't multiply the polynomials in increasing order of degree and still gets ac really fast. Any idea what is happening here? For reference, here is my solution: https://www.codechef.com/viewsolution/11938697
(25 Oct '16, 01:29)

answered 25 Oct '16, 00:28

answered 25 Oct '16, 02:09

The complexity is N * log N instead of N log ^ 2 N, using the idea described in editorial. This is because, last step of FFT multiplication would be most costly, enough, to ignore previous steps. answered 30 Dec '16, 08:53

The complexity is N * log N instead of N log ^ 2 N, using the idea described in editorial. This is because, last step of FFT multiplication would be most costly, enough, to ignore previous steps. answered 30 Dec '16, 08:54
