Question

http://courses.csail.mit.edu/6.046/spring04/handouts/prac-quiz2-sol.pdf

I'm confused as to the solution for the snowball question. To start with, I have two specific questions:

(1) Each pair $a_i,b_j$ will account for one term (and why ONE term)? What is meant by term here? The coefficient, $c_k$ of the polynomial C? Or maybe the $x$ value at the $kth$ spot?

(2) Why is $c_k$ the number of such pairs?

Was it helpful?

Solution

Here is the idea of the proof. Let $a_i,b_i$ be the distance thrown by the $i$th male/female. Using FFT, we calculate $$ \left(\sum_i x^{a_i}\right) \left(\sum_j x^{b_j}\right) = \sum_{i,j} x^{a_i+b_j}. $$ Each pair $i,j$ satisfying $a_i + b_j = k$ contributes one term $x^k$ to the polynomial on the right. Hence the coefficient of $x^k$ is the number of pairs $i,j$ such that $a_i + b_j = k$.

If things still aren't clear, I suggest you try a few examples.

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top