here is the problem from spoj that states
For a string of n bits x1,x2,x3,...,Xn the adjacent bit count of the string (AdjBC(x)) is given by
X1*X2 + X2*X3 + X3*X4 + ... + Xn-1 * Xn
which counts the number of times a 1 bit is adjacent to another 1 bit. For example:
AdjBC(011101101) = 3
AdjBC(111101101) = 4
AdjBC(010101010) = 0
and the question is : Write a program which takes as input integers n and k and returns the number of bit strings x of n bits (out of 2ⁿ) that satisfy AdjBC(x) = k.
I have no idea how to solve this problem. Can you help me to solve this ?
Thanks
Often in combinatorial problems, it helps to look at the set of values it produces. Using brute force I calculated the following table:
k 0 1 2 3 4 5 6
n +----------------------------
1 | 2 0 0 0 0 0 0
2 | 3 1 0 0 0 0 0
3 | 5 2 1 0 0 0 0
4 | 8 5 2 1 0 0 0
5 | 13 10 6 2 1 0 0
6 | 21 20 13 7 2 1 0
7 | 34 38 29 16 8 2 1
The first column is the familiar Fibonacci sequence, and satisfies the recurrence relation f(n, 0) = f(n-1, 0) + f(n-2, 0)
The other columns satisfies the recurrence relation f(n, k) = f(n - 1, k) + f(n - 1, k - 1) + f(n - 2, k) - f(n - 2, k - 1)
With this, you can do some dynamic programming:
INPUT: n, k
row1 <- [2,0,0,0,...] (k+1 elements)
row2 <- [3,1,0,0,...] (k+1 elements)
repeat (n-2) times
for j = k downto 1 do
row1[j] <- row2[j] + row2[j-1] + row1[j] - row1[j-1]
row1[0] <- row1[0] + row2[0]
swap row1 and row2
return row2[k]