You are not logged in. Please login at www.codechef.com to post your questions!

×

COUNTWAY - Editorial

4
1

PROBLEM LINK:

Practice
Contest

Author and Editorialist: Lalit Kundu
Tester: Kamil Debowski

DIFFICULTY:

medium-hard

PREREQUISITES:

combinatorics, fast-fourier 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:

======================
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$.

EXPLANATION:

================

Theorem 1:
It's a popular result using generating functions 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}}$.

Theorem 2:
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.

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})}{(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.

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:

tester solution 1
tester solution 2

asked 23 Oct '16, 23:57

darkshadows's gravatar image

5★darkshadows ♦
3.0k93164187
accept rate: 12%

edited 24 Oct '16, 03:10


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... :)

link

answered 24 Oct '16, 03:23

saar2119's gravatar image

5★saar2119
1213
accept rate: 0%

2
(25 Oct '16, 01:26) pranavarora6★
link

answered 25 Oct '16, 00:28

hanit1995's gravatar image

2★hanit1995
11
accept rate: 0%

I did Π(1+...+xi^fi) and got ac. Is there any advantage in doing Π (1−xi^(fi+1))/(1-x)

link

answered 24 Oct '16, 19:15

alei's gravatar image

7★alei
2315
accept rate: 0%

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) mishraiiit6★

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) pranavarora6★

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.

link

answered 30 Dec '16, 08:53

dreamplay's gravatar image

4★dreamplay
1485
accept rate: 0%

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.

link

answered 30 Dec '16, 08:54

dreamplay's gravatar image

4★dreamplay
1485
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,643
×1,240
×887
×334
×136
×37
×9

question asked: 23 Oct '16, 23:57

question was seen: 3,284 times

last updated: 30 Dec '16, 23:07