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?

Improve this question
$\endgroup$
1
  • 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
    Commented Nov 16, 2013 at 14:08

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
6
  • $\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
    Commented Oct 19, 2013 at 23:21
  • $\begingroup$ Moreover, what is $x^k$? Is it a coefficient? $\endgroup$
    – lars
    Commented Oct 19, 2013 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
    Commented Oct 19, 2013 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
    Commented Oct 20, 2013 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
    Commented Oct 20, 2013 at 0:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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