A Little Background
I was trying to solve this problem on SPOJ. It’s a dynamic-programming problem. I tried to find some recursive relation. I spent hours. But no breakthrough.
I even tried looking for hints in comments and I came to know it’s a 3D dynamic-programming problem. Some of the users were even able to reduce it to a 2D technique.
Then I realized I need to rethink the entire approach. So somehow, I started treating it like a combinatorics problem and I landed on a solution — a formula that guarantees linear time execution. I love moments like these when you solve an interesting problem with an uncommon approach. And that’s why I am writing this post.
The Problem
The problem involves dealing with bit strings. A bit string is basically a sequence where each term can have value either $0$ or $1$.
Usually, bit strings are represented without commas. So the bit string $1,0,0,1,0$ is abbreviated as $10010$.
Now we define a function $f(s)$ which takes a bit string $s = x_1 x_2 \ldots x_n$ and gives the output:
$$ f(s) = x_1 x_2 + x_2 x_3 + \ldots + x_{n-1} x_n $$
This function is what they call the adjacent bit count of $s$. This function basically tells us the number times the bit string $11$ appears in $s$.
E.g. $f(101)=0$, $f(1011)=1$, $f(111)=2$, $f(110111)=3$.
Now we’re ready to state our problem.
Given positive integers $n$ and $k$, find the number of bit strings $s$ of length $n$ which satisfies $f(s)=k$.
For example, let $n=5$ and $k=2$. The possible bit strings are $11100$, $01110$, $00111$, $11011$, $10111$, $11101$. So our answer is $6$.
Solution
We are given the fixed values $n$ and $k$. We introduce a variable value $a$ which we define as the number of continuous blocks of 1-bits in a bit string. Now onwards, we will refer to this as 1-block.
For example, $101110011$ has $a=3$ and $1010101$ has $a=4$.
If we fix the value of $a$, our problem becomes simpler as we will see later. We then have to calculate adjacent bit count for each possible value of $a$ and then sum them to obtain our final answer.
Before we jump to the actual solution, we need to observe a few things.
Let $m_1, m_2, \ldots ,m_a$ be the number of 1-bits in the $a$ 1-blocks from left to right respectively. E.g., for $101101$ we have $m_1 = 1$, $m_2 = 2$ and $m_3=1$.
Note the following points:
In a 1-block containing $m_i$ 1-bits, the bit string $11$ appears $m_i - 1$ times. This gives adjacent bit count for a single 1-block. So for the entire bit string, we must have $k = \sum_{i=1}^{a}\left(m_i -1\right) = {\sum m_i }-a$. So we get
$$ \text{number of 1-bits} = {\sum m_i} = k+a $$
Since a bit string consists of only zeros and ones, we get
$$ \text{number of 0-bits} = n-\sum m_i = n-k-a $$
Since $k \geq 1$, we must have at least one 1-block, and hence $a\geq1$. Also note that we must have at least $a-1$ 0-bits for separating the 1-blocks. This gives $a-1 \leq n-k-a \Rightarrow a \leq \frac{n-k+1}{2}$. So the range of $a$ is
$$ 1 \leq a \leq \left[\frac{n-k+1}{2}\right] $$
where $\left[x\right]$ denotes the floor function.
Now we move to the actual solution.
For a fixed value of $a$, we employ [Beggar’s Method]({% post_url 2018/2018-04-29-beggars-method %}) to our rescue. We take an empty bit string and break our problem into two parts.
Number of ways to fill 1-bits in the bit string: We have $k+a$ 1-bits, which we want to distribute in $a$ 1-blocks, which are currently empty. Number of ways to fill 0-bits in the bit string: We have $n-k-a$ 0-bits, which we want to distribute in the gaps between the 1-blocks.
So, for fixed $a$, our answer will be the product of above two values. Our final answer will be sum of these products.
Filling 1-bits
Imagine our $a$ 1-blocks as $a$ empty buckets lined up in a row from left to right, with their positions fixed. We need to find the number of ways we can distribute $k+a$ available 1-bits in them.
But we have to keep in mind that none of the bucket remains empty. So first, lets put one 1-bit in each of the buckets. Now, we have to distribute the remaining $k$ 1-bits in whatever way we wish.
Let $m_1, m_2, \ldots ,m_a$ be the distribution of remaining $k$ 1-bits in the buckets from left to right, respectively.
$$ m_1 + m_2 + \ldots + m_a = k, \quad m_i \geq 0 $$
By Beggar’s Method, we get
$$ \text{number of ways to fill 1-bits} = {^{k+a-1}C_{a-1}} \tag{1} $$
Filling 0-bits
We have $a$ buckets, which gives us $a+1$ gaps to fill zeros in.
The first and the last gaps can remain empty. But the inner $a-1$ gaps must have at least one 0-bit, otherwise we will have less than $a$ 1-blocks which contradicts that we have $a$ blocks.
So we distribute one 0-bit in each of the inner gaps. Now we can freely distribute the remaining $n-k-a-\left(a-1\right) = n-k-2a+1$ 0-bits in $a+1$ gaps.
Let $x_1, x_2, \ldots , x_{a+1}$ be the distribution of remaining 0-bits in gaps. Then we have to solve
$$ x_1 + x_2 + \ldots + x_{a+1} = n-k-2a+1, \quad x_i \geq 0 $$
Applying Beggar’s Method, we get
$$ \begin{align} \text{number of ways to fill 0-bits} & = {^{\left(n-k-2a+1\right)+\left(a+1\right)-1}C_{\left(a+1\right)-1}}\ & = {^{n-k+1-a}C_{a}} \tag{2} \end{align} $$
Final Answer
As discussed earlier, our final answer is the summation of product of the binomial coefficients obtained in $\left(1\right)$ and $\left(2\right)$.
$$ \sum_{a=1}^{\left[\frac{n-k+1}{2}\right]} {^{k+a-1}C_{a-1}} \cdot {^{n-k+1-a}C_{a}} \tag{3} $$
Conversion To Code
To achieve linear runtime, it’s clearly visible that we have to run a for loop on $a$, the number of 1-blocks. In each pass of loop we have to calculate the product of binomial coefficients in constant time.
But the usual dynamic programming method takes $\mathcal{O}\left( q^2 \right) $ time for calculating $^{q}C_{r}$. But we can do it in constant time if we know the binomial coefficients in last pass. We do it using the following formula
$$ ^{q}C_{r} = \frac{q}{r} \cdot {^{q-1}C_{r-1}} \tag{4} $$
Applying the above formula on the binomial coefficient in $\left(1\right)$, we get
$$ {^{k+a-1}C_{a-1}} = \frac{k+a-1}{a-1} \cdot {^{k+\left(a-1\right)-1}C_{\left(a-1\right)-1}} \tag{5} $$
For the binomial coefficient $\left(2\right)$, we substitute $p=n-k+1$ so as to make it look cleaner. ${^{n-k+1-a}C_{a}}$ becomes ${^{p-a}C_{a}}$. Using identity $\left(4\right)$ on this, we get
$$ {^{p-a}C_{a}} = \frac{ \left(p-2a+1\right) \left(p-2a+2\right) }{ a \left(p-a+1\right) } \cdot {^{p-\left(a-1\right)}C_{a-1}} \tag{6} $$
Note that the initial values of these coefficients i.e. when $a=1$, are $1$ and $n-k$ respectively. Keeping this in mind and using equations $\left(3\right)$ and $\left(6\right)$, this is what our final code solution looks like.
long long x=n-k, y=1, p=n-k+1, sum=0;
sum += x*y;
for(int a=2; a<=p/2; a++){
x = (x*(p-2*a+1)*(p-2*a+2))/(a*(p-a+1));
y = (y*(k+a-1))/(a-1);
sum += x*y;
}
As you can see, the for loop runs $p/2$ times. Hence, the time complexity of program is $\mathcal{O}\left(n-k\right)$.
You can find the complete program here.