How many possibilities exists to build a 2^n tower (with base area 2x2) of 2x1x1 Blocks? This has to be a divide and conquer algorithm, as I understood so far. I figured out the O(2^n), but I would like to solve this problem in polynomial time.
The main problem in my case is to figure out the "conquer" part.
Could somebody give me an advise how to solve this problem in polynomial time?
Let F(n) be the number of ways of constructing a tower of height n from a flat base, and S(n) be the number of ways of constructing a tower of height n from a base where half is filled in.
Then F(n) = 2F(n-1) + 4S(n-1), and S(n) = F(n-1) + S(n-1).
That's because if you start with a flat base, there's two ways of filling the bottom layer completely in without any bits sticking up, and there's 4 ways of putting down a piece flat, with two pieces sticking up. And similarly, if you have a half-filled base, you can either complete the layer by adding a piece lying down, or add two more sticking up pieces, which half fills the layer above.
Then, you can express this as a matrix-vector multiply (in ASCII art):
F(n) = (2 4) (F(n-1))
S(n) = (1 1) (S(n-1))
and so:
F(n) = (2 4)^n (F(0))
S(n) = (1 1) (S(0))
Since F(0) = 1 and S(0) = 0, you have:
F(n) = (2 4)^n (1)
S(n) = (1 1) (0)
You can compute the matrix power in O(log n) time using exponentiation by squaring. This gives you an O(n) algorithm for finding the ways of building the 2^n height tower.
A different (divide-and-conquer) approach is to count ways of building a tower of height 2^n, where the bottom layer is either complete or half-filled vertically, or half-filled horizontally. Then you can halve the problem each time by counting ways to combine two of the 9 different half-towers together. It's more complicated to work out though, and still O(n) since you can't use the matrix power trick because some squared terms appear.