Olympiad Problem

[jumper007]

I think I failed this one.

--- The olympiad took place a few hours ago. ---

Colours

Miruna loves painting. In the last vacantion she went to her grandmother, and as she was bored, she started to paint her grandmother's house fence.
The fence is made of N boards one near the others. Miruna found in her grandmother's garage 5 boxes with colours. The colours are: While, Blue, Red, Green, Yellow. When she painted the fence, Miruna followed these rules:
- If a board is White, the next board is Blue;
- If a board is Blue, the next one is either White, or Red;
- If a board is Red, the next one is either Blue, or Green;
- If a board is Green, the next one is either Red, or Yellow;
- If a board is Yellow, then the next one is Green.
After she finished her "art", she asked herself in how many DIFFERENT ways she could paint the fence. Answer her question.

RESTRICTIONS
For 25% of tests 1 <= N <= 45
For the others N <= 5000

Example:

colours.in  colours.out
4           24 

----------
I could find that

Number of solutions for WHITE = No. solutions for Yellow; No. solutions for Red = Blue = Green. So Number of TOTAL solutions = 2x White + 3x Red.
Also, I calculated manually the solutions for  1<= N <=7

N=1 => 1
N=2 => 8
N=3 => 12
N=4 => 24
N=5 => 30
N=6 => 44
N=7 => 128

Please help me. I have to say that I'm in the 10th grade, so I do not know any GRAPH THEORY (...) (I figured it out that it can be solved with the Graph Theory, but I have no Calculus knowladge ... )

[Kyon]

So exactly what is asked? Do we need to find a general method of calculating the value in mathematical means?

By the way, wouldn't N=1 mean there's only a single board to be painted and, given there's five colors, mean that should be 5?

EDIT:
I used my Graftal program to simulate this problem, it gave me these results:

N=1 => 5
N=2 => 8
N=3 => 14
N=4 => 24
N=5 => 42
N=6 => 72
N=7 => 126
N=8 => 216
N=9 => 378
N=10 => 648
N=11 => 1134

I'll post the code if you want.

EDIT:
This thread is double-posted:
http://www.cplusplus.com/forum/general/63535/
http://www.cplusplus.com/forum/windows/63537/

[hamsterman]

Here's a brute haskell solution : http://ideone.com/5ctfo

I'll think about something more sophisticated..

[JLBorges]

next color = case color of
  White -> [Blue]
  Blue -> [White, Red]
  Red -> [Blue, Green]
  Green -> [Red, Yellow]
  Yellow -> [Green]

Hmm... For N==5, would this count as one of the ways of painting the fence?
(Though the next one to a Yellow is a White.)

White, Blue, Red, Green, Yellow, White (the first board)

[Kyon]

I figured out the way.

The formula for all combinations is (indexed with n) is:
C_n = 2*W_n + 2*B_n + R_n

In which W_n, B_n and R_n respectively indicate the amount of combinations possible starting with just White, just Blue or just Red (times two since White acts the same as Yellow but mirrored and Blue acts the same as Green mirrored).

After looking at the results, you'll find that B_n = W_n+1 and that R_n=(W_n+W_n+2)/2.

C_n = 2*(W_n + W_n+1) + (W_n + W_n+2)/2

And W_n is given in a recursive way where W_n=W_n-1+W_n-2 when n is even and W_n=2*W_n-1 when n is odd.

My task is done here.

[tition]

@Kyon: nice solution mate!

Here is another mathematical view.

next color = case color of
White -> [Blue]
Blue -> [White, Red]
Red -> [Blue, Green]
Green -> [Red, Yellow]
Yellow -> [Green]

Therefore

W_{n+1} (0 1 0 0 0)(W_n)
B_{n+1} (1 0 1 0 0)(B_n)
R_{n+1}=(0 1 0 1 0)(R_n)
G_{n+1} (0 0 1 0 1)(G_n)
Y_{n+1} (0 0 0 1 0)(Y_n)

Now in order to find a close form formula, you find the eigenvectors/eigenvalues of the above matrix and then diagonalize to get nice close-form formulas...

Have you studied linear algebra?

[helios]

Hey, that's an idea. Another solution is
M=[
0 1 0 0 0
1 0 1 0 0
0 1 0 1 0
0 0 1 0 1
0 0 0 1 0
]
f(n)=sum(M^(n-1))
where sum returns the sum of all the elements in the matrix.

EDIT: Anyone else noticed that f(5000)>1E+1100?

[tition]

Yep; the good news is that any matrix can be written in the form

M= XDX^{-1}, where D is either a diagonal matrix, or is made up of Jordan cells
(Jordan cell = has a constant on the main diagonal (top left to bottom right) and 1's in the diagonal directly above it, for example:

(a 1 0)
(0 a 1) 
(0 0 a)

)
In addition, if the starting matrix were symmetric, you always get X^{-1}MX=D to be diagonal.

What does this help?
Well,
(X D X^{-1})^n=X D^n X^{-1}
Furthermore, raising a diagonal matrix to the n^th power is dead easy, for example:

(a 0)^n 
(0 b)

equals

(a^n  0)
(0  b^n)

So helios, the speed of growth of f(n) will be that of a^n where a is the largest entry you see on the diagonal of the matrix D. You can compute that explicitly actually.

The entries on the diagonal of the matrix D are called "eigenvalues".

[helios]

I was rather thinking something along the lines of
next_power(x)[i][j]=x[i][j-1]+x[i][j+1] (don't add things outside the matrix)
which requires simpler arithmetic.

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <ctime>

const size_t N=2000;

class BigNat{
    char *array;
public:
    BigNat(unsigned n=0){
        this->array=new char[N];
        this->clear();
        for (size_t a=0;n;n/=10,a++)
            this->array[a]=n%10;
    }
    ~BigNat(){
        delete[] this->array;
    }
    void clear(){
        memset(this->array,0,N);
    }
    BigNat &operator=(const BigNat &b){
        memcpy(this->array,b.array,N);
        return *this;
    }
    BigNat &operator+=(const BigNat &b){
        char carry=0;
        for (size_t a=0;a<N;a++){
            this->array[a]+=b.array[a]+carry;
            carry=this->array[a]/10;
            this->array[a]%=10;
        }
        return *this;
    }
    friend std::ostream &operator<<(std::ostream &,const BigNat &);
};

std::ostream &operator<<(std::ostream &stream,const BigNat &bi){
    size_t a=N-1;
    for (;a>0 && !bi.array[a];a--);
    do {
        stream <<char(bi.array[a]+'0');
    }while (a--);
    return stream;
}

void next_power(BigNat *dst,BigNat *src){
    for (int i=0;i<5;i++){
        for (int j=0;j<5;j++){
            BigNat &d=dst[i+j*5],
                *s1=src+(i+(j-1)*5),
                *s2=src+(i+(j+1)*5);
            if (!j)
                d=*s2;
            else if (j==4)
                d=*s1;
            else{
                d=*s1;
                d+=*s2;
            }
        }
    }
}

void f(BigNat &r,int n){
    BigNat matrixA[25]={
            1,0,0,0,0,
            0,1,0,0,0,
            0,0,1,0,0,
            0,0,0,1,0,
            0,0,0,0,1
        },
        matrixB[25],
        *dst=matrixA,
        *src=matrixB;
    for (size_t a=1;a<n;a++){
        std::swap(dst,src);
        next_power(dst,src);
    }
    r=dst[0];
    for (size_t a=1;a<25;a++)
        r+=dst[a];
    /*
    for (int i=0;i<5;i++){
        for (int j=0;j<5;j++){
            std::cout <<dst[i+j*5]<<' ';
        }
        std::cout <<std::endl;
    }
    */
}

int main(){
    clock_t t0,t1;
    t0=clock();
    BigNat n;
    f(n,5000);
    t1=clock();
    std::cout <<n<<std::endl;
    std::cout <<std::endl<<t1-t0<<std::endl;
    return 0;
}

[Kyon]

Well, my solution was close, I fixed a few flaws in it. I posted all that in a different version of this thread (there's three in total).

Excel document with some simple calculations in it:
http://depositfiles.com/files/85sjy53qe