1
$\begingroup$

Question

The convolution $a*b=\left(c_{0},c_{1},\ldots,c_{n+m-2}\right)$ of two vectors $\left(a_{0},\ldots,a_{n-1}\right)$ and $\left(b_{0},\ldots,b_{m-1}\right)$ is defined as follows: $$ \left(a*b\right)_{i}=c_{i}=\sum_{j=0}^{i}a_{j}b_{i-j} $$

Given that by using the $FFT$ algorithm the convolution can be calculated in $O\left(n\log n\right)$, suggest an algorithm that calculates the number of ways to generate each number in $\left\{ n,\ldots,6n\right\} $ by throwing $n$ dice in $O\left(n\log n\right)$.


My Take

I tought on defining the following vectors: $$ V_{A}\left[i\right]=V_{B}\left[i\right]=\begin{cases} 1 & \text{i is a possible result for n dice throws}\\ 0 & \text{else} \end{cases} $$ For example, if n = 2 then: $$ V_{A}=V_{B}=\left[\underbrace{0}_{1},\underbrace{1}_{2},\underbrace{1}_{3},\underbrace{1}_{4},\underbrace{1}_{5},\underbrace{1}_{6},\underbrace{1}_{7},\underbrace{1}_{8},\underbrace{1}_{9},\underbrace{1}_{10},\underbrace{1}_{11},\underbrace{1}_{12}\right] $$ So the convolution would be: $$ c_{i}=\sum_{j=0}^{i}V_{A}\left[j\right]V_{B}\left[i-j\right] $$ when $c_{i}$ contains the possible ways to get $i$ as the sum of $n$ throws.

For example: $$ c_{2}=\underbrace{V_{A}\left[0\right]V_{B}\left[2\right]}_{0}+\underbrace{V_{A}\left[1\right]V_{B}\left[1\right]}_{1}+\underbrace{V_{A}\left[1\right]V_{B}\left[0\right]}_{0}=1 $$ So there is only one way to get 2 as the sum of two dice throws.

Well, I think it works for $n=2$ but it gets complicated for $n>2$, and I don't think it works in $O\left(n\log n\right)$ anymore.

When $n=3$ I will define: $$ V_{A}=V_{B}=\left[\underbrace{0}_{1},\underbrace{0}_{2},\underbrace{1}_{3},\underbrace{1}_{4},\underbrace{1}_{5},\underbrace{1}_{6},\underbrace{1}_{7},\ldots,\underbrace{1}_{23},\underbrace{1}_{24}\right] $$

So for example: $$ c_{8}=\underbrace{V_{A}\left[0\right]V_{B}\left[8\right]}_{0}+\ldots+\underbrace{V_{A}\left[3\right]V_{B}\left[5\right]}_{1}+\underbrace{V_{A}\left[4\right]V_{B}\left[4\right]}_{1}+\underbrace{V_{A}\left[5\right]V_{B}\left[3\right]}_{1}+\ldots+\underbrace{V_{A}\left[8\right]V_{B}\left[0\right]}_{0}=3 $$

That is incorrect, because in this case I need to find the number of possible ways to get 3,4 and 5.

This is where I got stuck. I don't know if my idea is good and if it's possible to use it and stay at $O\left(n\log n\right)$. I think it gets recursive and complicated.

$\endgroup$
2
  • $\begingroup$ There is a closed formula for the number of different ways to generate a number $k$ from $n$ dice throws (each die has $6$ sides). What is stopping you from directly calculating this formula? $\endgroup$
    – nir shahar
    Jan 8 at 15:40
  • $\begingroup$ @nirshahar These are not the terms of the question so I guess they did not expect me to use a closed formula $\endgroup$
    – Tal Barda
    Jan 8 at 19:20
0
$\begingroup$

FFT allows you to multiply two degree $d$ polynomials in $O(d\log d)$.

In your case, you want to compute $(x+x^2+x^3+x^4+x^5+x^6)^n$. Using repeated squaring and FFT, you can compute this in $O(n\log n)$. The coefficient of $x^k$ gives you the number of ways to obtain $k$ by throwing $n$ dice.

$\endgroup$

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.