http://courses.csail.mit.edu/6.046/spring04/handouts/prac-quiz2-sol.pdfI'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?
Snowball Question FFT
algorithms;fourier transform;polynomials
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.