Answers to: COUNTWAY - Editorialhttps://discuss.codechef.com/questions/86441/countway-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/COUNTWAY">Practice</a><br>
<a href="http://www.codechef.com/COOK75/problems/COUNTWAY">Contest</a> </p>
<p><strong>Author and Editorialist:</strong> <a href="http://www.codechef.com/users/darkshadows">Lalit Kundu</a><br>
<strong>Tester:</strong> <a href="http://www.codechef.com/users/errichto">Kamil Debowski</a> </p>
<h1>DIFFICULTY:</h1>
<p>medium-hard</p>
<h1>PREREQUISITES:</h1>
<p>combinatorics, fast-fourier transform, divide and conquer</p>
<h1>PROBLEM:</h1>
<p>Given an array of integers $A_1, A_2, ..., A_N$ and an integer $K$, count number of ways to choose a multiset(<i>i.e.</i> a set with duplicate elements) of size $K$. Two multisets are different iff count of any element is different in both.</p>
<h1>QUICK EXPLANATION:</h1>
<p>====================== <br>
Answer is coefficient of $x^K$ in polynomial $\dfrac{(1 - x^{f_1 + 1})*(1 - x^{f_2 + 1})*....*(1 - x^{f_k + 1})}{(1-x)^{k}}$, where $f_1, f_2, ..., f_k$ are frequencies of $k$ distinct elements present in the array $A$. Numerator of this polynomial can be evaluated using any fast polynomial multiplication algorithm since it's degree is $N$.</p>
<h1>EXPLANATION:</h1>
<p>================</p>
<p><strong>Theorem 1</strong>: <br>
It's a popular result using <a href="www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15251-s10/Site/.../lecture06.ppt">generating functions</a> that number of integral solutions to equation $x_1 + x_2, ..., + x_r = N$, where $x_i \le l_i$ are coefficient of $x^N$ in $(1 + x + x^2 + ... + x^{l_1})*1 + x + x^2 + ... + x^{l_2})*...*1 + x + x^2 + ... + x^{l_r})$, which we re-write as $\dfrac{(1 - x^{l_1 + 1})*(1 - x^{l_2 + 1})*....*(1 - x^{l_r + 1})}{(1-x)^{r}}$.</p>
<p><strong>Theorem 2</strong>: <br>
Coefficient of $x^k$ in $(1-x)^{-N}$ is $C(N + k - 1, k)$, where $C(i, j)$ is number of ways to choose $j$ distinct elements from a set of $i$ distinct elements. This can be proved using Taylor series expansion.</p>
<p>We'll avoid the proof here, but you can follow above link to explore more.</p>
<p>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})}{(1-x)^{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.</p>
<p>For multiplication of two polymials you can use FTT or even Karatsuba. For further reading on these algorithms you can read <a href="https://en.wikipedia.org/wiki/Multiplication_algorithm#Fast_multiplication_algorithms_for_large_inputs">this</a>.</p>
<h1>AUTHOR'S, TESTER'S SOLUTIONS:</h1>
<p><a href="http://www.codechef.com/download/Solutions/COOK75/Setter/COUNTWAY.cpp">tester solution 1</a> <br>
<a href="http://www.codechef.com/download/Solutions/COOK75/Tester/COUNTWAY.cpp">tester solution 2</a> </p>enFri, 30 Dec 2016 08:54:02 +0530Answer by dreamplayhttps://discuss.codechef.com/questions/86441/countway-editorial/89600<p>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.</p>dreamplayFri, 30 Dec 2016 08:54:02 +0530https://discuss.codechef.com/questions/86441/countway-editorial/89600Answer by dreamplayhttps://discuss.codechef.com/questions/86441/countway-editorial/89599<p>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.</p>dreamplayFri, 30 Dec 2016 08:53:51 +0530https://discuss.codechef.com/questions/86441/countway-editorial/89599Answer by hanit1995https://discuss.codechef.com/questions/86441/countway-editorial/86533<p><a href="https://www.hackerrank.com/challenges/emma-and-sum-of-products/editorial">https://www.hackerrank.com/challenges/emma-and-sum-of-products/editorial</a></p>hanit1995Tue, 25 Oct 2016 02:09:57 +0530https://discuss.codechef.com/questions/86441/countway-editorial/86533Answer by hanit1995https://discuss.codechef.com/questions/86441/countway-editorial/86529<p><a href="http://web.cecs.pdx.edu/~maier/cs584/Lectures/lect07b-11-MG.pdf">http://web.cecs.pdx.edu/~maier/cs584/Lectures/lect07b-11-MG.pdf</a></p>hanit1995Tue, 25 Oct 2016 00:28:29 +0530https://discuss.codechef.com/questions/86441/countway-editorial/86529Answer by aleihttps://discuss.codechef.com/questions/86441/countway-editorial/86500<p>I did Π(1+...+xi^fi) and got ac. Is there any advantage in doing Π (1−xi^(fi+1))/(1-x)</p>aleiMon, 24 Oct 2016 19:15:42 +0530https://discuss.codechef.com/questions/86441/countway-editorial/86500Answer by saar2119https://discuss.codechef.com/questions/86441/countway-editorial/86455<p>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... :)</p>saar2119Mon, 24 Oct 2016 03:23:08 +0530https://discuss.codechef.com/questions/86441/countway-editorial/86455