0
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Could you copy the relevant information into the question (with attribution of course!) to make the question as self-contained as possible? $\endgroup$ – Luke Mathieson Nov 16 '13 at 14:08
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ First you didn't even try to answer my specific questions. And now we have 3 summation signs, where there were none in the solution. So I am now more confused. $\endgroup$ – lars Oct 19 '13 at 23:21
  • $\begingroup$ Moreover, what is $x^k$? Is it a coefficient? $\endgroup$ – lars Oct 19 '13 at 23:23
  • $\begingroup$ Finally, you need an argument to go from Each pair i,j satisfying $a_i+b_j=k$ contributes one term $x^k$ to the polynomial on the right. To the claim that the coefficient of $x^k$ = number of pairs that equal $k$ $\endgroup$ – lars Oct 19 '13 at 23:29
  • $\begingroup$ Here $x^k$ is a monomial ($x$ is known as a "formal variable"). You can also think of it as a polynomial having a single monomial. I suggest you go over the FFT algorithm again - they must have covered polynomials when they discussed the algorithm, especially given the application to multiplying univariate polynomials. $\endgroup$ – Yuval Filmus Oct 20 '13 at 0:20
  • $\begingroup$ Re your other comment, I agree that an argument is required, but only if you want to be very formal. Otherwise, I suggest you try a few examples and see how it works. $\endgroup$ – Yuval Filmus Oct 20 '13 at 0:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.