Using FFT to Speed Up DP

Problem link: Counting Road Networks | HackerRank.

You are supposed to count the number of connected undirected labeled graphs with $n$ vertices. Algorithms with $O(n \log^2 n)$ time complexity are preferable.

A Dynamic-Programming Algorithm

Let $f(n)$ be the answer for $n$. The first idea to compute $f(n)$ is subtracting the number of disconnected graphs from the total number. The total number of size-$n$ graphs is $g(n) := 2^{\binom{n}{2}}$. How to count the disconnected graphs? Let’s consider the size $m$ of the connected component containing the vertex labeled with 1. Since the graph is disconnected, $m$ cannot be $n$. Then the number of disconnected graphs where the connected component containing vertex 1 is a certain one with size $m$ is exactly $f(m) \cdot g(n-m)$. Now we have an $O(n^2)$-time dynamic-programming algorithm as follows. $$ f(n) = g(n) - \sum_{m=1}^{n-1} \binom{n-1}{m-1} \cdot f(m) \cdot g(n - m) $$

Expression Rearrangement

If we unfold the binomial coefficients, we will have $$ \frac{f(n)}{(n-1)!} = n \cdot \frac{g(n)}{n!} - \sum_{m=1}^{n-1} \frac{f(m)}{(m-1)!} \cdot \frac{g(n-m)}{(n-m)!} $$ Let $F(n) := \frac{f(n)}{(n-1)!}$ and $G(n) := \frac{g(n)}{n!}$. Moreover, let’s set $F(0)$ to $0$ and then we have $$ F(n) = n \cdot G(n) - \sum_{m=0}^{n-1} F(m) \cdot G(n-m) $$ Note that we already have a convolution-like term in the formula.

An Optimization Based on FFT

We will use Fast Fourier transform (FFT) as an $O(n \log n)$-time algorithm to compute convolution of length $n$.

First of all, $G(n)$ are easy to compute so we can pre-process them. Now we are going to use a divide-and-conquer scheme. Let $solve(l,r)$ be a procedure that computes $F(n)$ for all $n \in [l,r)$. In addition, we add the following invariant to this procedure:

When invoking $solve(l,r)$, we already compute for each $n \in [l,r)$, the partial convolution $\sum_{m=0}^{l-1} F(m) \cdot G(n-m)$, and store them in $H(n)$.

Then our algorithm proceeds as follows.

• If $l+1=r$, we set $F(l)$ to $l \cdot G(l) - H(l)$.
• Otherwise, let’s invoke $solve(l,k)$ first where $k = \frac{l+r}{2}$, i.e., the middle point. Now we already solve the first half of the problem. To become able to invoke $solve(k,r)$ to complete the second half, we need to do something to maintain the invariant above. In essence, we need to update $$ H(n) \gets H(n) + \sum_{m=l}^{k-1} F(m) \cdot G(n-m) $$ for each $n \in [k,r)$. Here comes the chance for optimization. What we really want to compute is the convolution of $F[l,k)$ and $G[0,r-l)$! Let the convolution result be $C$ and indeed we have $$ C(n) = \sum_{m=l}^{k-1} F(m) \cdot G(n-m) $$ for each $n \in [k,r)$. After performing $H(n) \gets H(n) + C(n)$ for each $n \in [k,r)$, we reestablish the invariant and we can recurse to $solve(k,r)$.

Finally, let’s estimate the time complexity of the algorithm above. Let $T(n)$ be the running time of $solve(l,r)$ with $n=r-l$. By using FFT to compute the convolution, we can establish the following $$ T(n) = 2T(\frac{n}{2}) + O(n \log n) $$ Then by the Master Theorem we derive that $T(n) = O(n \log^2 n)$.

What’s More

For those who could read Chinese, CDQ’s divide-and-conquer is a good reference about applications of the divide-and-conquer scheme in this post.