Number of combinations with LEGO plastic bricks C++

Question

You have some LEGO plastic bricks, all bricks are 1x1x1. Also you have one tile, 1xN (N <= 80), on which you should place the LEGO bricks. You can order them in sequences (one sequence is correct if it has 3 or more consecutive bricks), also you must have at least 1 empty space between 2 sequences. You should calculate the number of different combination you can place the bricks on the tiles.

Here's an example:

If the tile is 1x7, there are 17 different combinations.

input : 7 output : 17

_{(source: mendo.mk)}

Also if you have no bricks it's counted as 1 combination.

I have worked on this problem and i found the way to calculate possible combinations of if the max length of the tile is 14 (3 sequences). I found it using for loops.

My biggest problem is the huge number of for loops that i need to run. For example, for 1 sequence i use 1 for loops, for 2 sequences 2 loops + 1 for 1 sequnce...so if i use all 80 bricks, i can create 20 sequence and i will have to use over 210 for loops which is huge number. So it'll be good if i can nest them in one. I tried it and it get messy and it doesn't give correct answers.

New code:

#include <iostream>
using namespace std;
int main()
{
    long long int places, combinations = 1;
    cin >> places;
    long long int f[80], g[80];
    f[0] = 0;
    f[1] = 0;
    f[2] = 0;
    g[0] = 1;
    g[1] = 1;
    g[2] = 1;
    for(int i = 3; i<=places; i++)
    {
        f[i] = f[i-1] + g[i-3];
        g[i] = f[i-1] + g[i-1];
    }
    combinations = f[places] + g[places];
    cout << combinations;
    return 0;
}

Answer 1

If this is a counting problem (not outputting combination, rather just counting them) it's an easy one. Assume we solved it for n ≥ 3 now to solve it for n+1, we solve it by induction:

Assume f is a function that shows the number of possible ways such that the last item is a brick. Analogously g is a function that shows the number of possible ways such that the last item is not brick. Let define h = f+g, to be the number of all possible ways.

So we have:

f(n+1) = f(n) + g(n-2)
g(n+1) = g(n) + f(n)

With initial condition:

for n=0,1,2: g=1, f= 0.
for n = 3: g=1,f=1

Samples:

n=4: g=2,f=2 ==> h=4
n=5: g=4, f= 3 ==> h=7
n=6: g=7, f= 4 ==> h=11
n=7: g=11,f=6 ==> h=17

We can solve it with one for loop in O(n).

---

Why:

f(n+1) = f(n) + g(n-2)
g(n+1) = g(n) + f(n)

First, let prove first part:

Remember that we assumed f(n) is a working solution which has a plastic brick in the last item, and g(n) is a working solution which doesn't have a brick in the last item.

f(n+1) can be obtained from f(n) by adding one brick at the last place. Also f(n+1) can be obtained by adding three brick after g(n-2), it means cells of n-1,n,n+1.

Note that we can't add brick after g(n-1) or g(n) to create a valid solution for f(n+1) because they are not valid solutions (number of consecutive bricks is less than 3). Also, note that we don't need to count the number of ways which arises by adding bricks after g(n-3) because they are previously enumerated by f(n). So we have f(n+1) = f(n) + g(n-2).

In the same way we can prove g(n+1) = f(n)+g(n) this case is easier, because g(n+1) simply can be made from any valid solution up to n, as there is no 3 consecutive brick barrier here, they can come after any valid solution.

Answer 2

As a person with math training, rather than CS, I feel obliged to mention that, while Saeed Amiri's algorithm is very nice and would probably work fast enough for N up to a few millions (with constant memory, of course), there is a better algorithm from the time perspective.

I will pick up where he has left:

f(n+1) = f(n) + g(n-2)
g(n+1) = f(n) + g(n)

Since f and g are discrete functions, you can treat them as sequences. This becomes a linear system of recurrence relations, then. Luckily, a system like this can be completely solved, so that the explicit form of f and g can be presented.
Unfortunately, SO does not seem to support MathJax like math.SE, so I apologize for the low quality of the equations from here on.
Let

     | f(n) |
     |f(n-1)|
u(n)=|f(n-2)|
     | g(n) |
     |g(n-1)|
     |g(n-2)|

That is, u(n) is a vector row. Then, the following is true:

|f(n+1)|   |1 0 0 0 0 1|   | f(n) |
| f(n) |   |1 0 0 0 0 0|   |f(n-1)|
|f(n-1)| = |0 1 0 0 0 0| . |f(n-2)|
|g(n+1)|   |1 0 0 1 0 0|   | g(n) |
| g(n) |   |0 0 0 1 0 0|   |g(n-1)|
|g(n-1)|   |0 0 0 0 1 0|   |g(n-2)|

What follows from this is, that u(n) = A * u(n-1), where A is the matrix above.
Then, u(n) = (A^(n-2)) * u(2), where u(2) is the vector, containing the initial values to the problem. This, in turn, gives an algorithm with O(log(n)) complexity, since you can use fast exponentiation to calculate (A^(n-2)) and then multiply it to u(2).

Of course, any such technique would probably require a BigInt of some sort, since otherwise the overflow is pretty much guaranteed.

Also note that this technique can be applied one step further:
You can find the eigenvectors and eigenvalues of A and then decompose u(2) into the eigenvectors. Then, you will have a closed form for both f(n) and g(n).

I strongly advise you against an algorithm based on the closed form
It almost certainly will involve high-precision floating-point calculations (unless all eigenvalues are integers, which is highly unlikely), which are of at least this complexity from programming perspective, and are not generally constant-time operations. Of course, neither are BigInt operations. So a constant-time algorithm is generally not feasible, plus you probably do not even need the O(log(n)), since for most uses the linear is good enough.

Note
The technique described here can be used in a variety of problems and is of extreme use in dynamic optimization problems. Plus, usually people are pretty impressed when they see this for the first time ;)