Olympiad Problem

jumper007 (435)
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:

1
2
 
colours.in  colours.out
4           24



----------
I could find that 
1
2
3
4
5
6
7
8
9
10
 
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 ... )
Last edited on
Stewbond (2827)
Visualizing it like this can help but I can't do your homework.
1
2
3
4
 
White-->Blue-->Red-->Green-->Yellow
    ^   |  ^   | ^   |   ^     |
    |   |  |   | |   |   |     |
    =====  ===== =====   =======
Last edited on
jumper007 (435)
Not a homework for goodness sake!!! I was there at the olympiad and couldnt do this problem!!!
ne555 (10692)
I don't see the difference.
5000 is quite low. I guess that you could simply simulate the process

solutions = 2x White + 3x Red.
¿eh?
Last edited on
Kyon (912)
Don't double post, please.
http://www.cplusplus.com/forum/lounge/63538/
http://www.cplusplus.com/forum/windows/63537/

My post that was over there:
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?

I used my Graftal program to simulate this problem, it gave me these results:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
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
N=12  => 1944
N=13  => 3402
N=14  => 5832
N=15  => 10206
N=16  => 17496
N=17  => 30618
N=18  => 52488
N=19  => 91854
N=20  => 157464
N=21  => 275562
N=22  => 472392
N=23  => 826686
N=24  => 1417176

I'll post the code if you want.
Last edited on
jumper007 (435)
If you post the code it will help me better understand what I had to do actually... So I would appreciate it. Yes >.> N=1 => 5... My bad...
jumper007 (435)
@ne555

I guess that you could simply simulate the process


For the love of GOD!! HOW? That's what I'm asking for... -.-

EDIT : Is there any mathematical recursion that can be used to define the number requested ?
Last edited on
Kyon (912)
I figured out the way.

The formula for all combinations is (indexed with n) is:
Cn = 2*Wn + 2*Bn + Rn

In which Wn, Bn and Rn 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 Bn = Wn+1 and that Rn=(Wn+Wn+2)/2.

Cn = 2*(Wn + Wn+1) + (Wn + Wn+2)/2

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

My task is done here.
jumper007 (435)
O_O Okey... I got to start with RElearning math then ...
ne555 (10692)
Simulation (with dynamic programming)
Suppose that you've got a matrix qty[ colour ][ n_block] that tells you the number of ways to paint if you start with 'colour'.
So qty[ x ][ 1 ] = 1
To know the total we simply add the corresponding column.

Now suppose that you've got N blocks and started with 'red' ¿how many ways then?
After red it can only be 'blue' or 'green' so we could say qty[ red ][ N ] = qty[ blue ][ N-1 ] + qty[ green ][ N-1] (because we know those previous values)
You apply the same procedure to the other colours, and construct the matrix.

@Kyon the sybil: ¿how much time? ¿and how many results did you need to see?
Last edited on
Kyon (912)
The pattern started to show itself after 8 results for me (looking at Cn, Wn, Bn and Rn), but I checked until 27 to confirm it.

The program I used for it was basically done already, I just had to change the inputs. I used my Graftal program for the simulation ( to see what graftals are: http://en.wikipedia.org/wiki/Graftal ):
main.cpp 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
#include "Graftal.h"
#include <ctime>

using namespace std;

int main()
{   CRuleSet set;
    set.add(CRule("W")>>"B");
    set.add(CRule("B")>>"WR");
    set.add(CRule("R")>>"BG");
    set.add(CRule("G")>>"RY");
    set.add(CRule("Y")>>"G");
    cout << set << endl;
    std::string x("R");
    for(unsigned u=1;u<=30;u++)
    {   cout << "N="<< u << "  => " << x.size() << endl;
        set.applyrules(x);}
    return 0;}


This calculates Rn. If you want to calculate Wn, use "W" instead of "R". If you want to calculate Bn, use "B" instead of "R". If you want to calculate Cn, use "WBRGY" instead of "R".

Graftal.h 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
 
/*
** Name:          Graftal.h
** Functionality: Adds CRule and CRuleSet classes to simulate regular, stochastic and context sensitive graftal grammars.
** Made by:       T. "Kyon" Westendorp
** Example:

CRuleSet graftal;
graftal.add(CRule("1","1","1")>>"1[0]1" // If there is a 1 in between a 1 and a 1, there is a 50% chance it will change into 1[0]1
                              >>"1");   // If there is a 1 in between a 1 and a 1, there is a 50% chance of not changing
graftal.add(CRule("1")>>"11");  // Change 1 into 11
graftal.add(CRule("0")>>"1[0]0" // 50% chance of changing 0 into 1[0]0
                      >>"0");   // 50% chance of not changing

std::string x = "0"; // Apply the rules to this axiom

for(unsigned u=0;u<=10;u++) // Evaluate the outcome for the first 10 steps (first printing the axiom)
{
    cout << u << " " << x << endl;
    graftal.applyrules(x);
}

*/

#ifndef GRAFTAL_H_INCLUDED
#define GRAFTAL_H_INCLUDED

#include <algorithm>
#include <iterator>
#include <iostream>
#include <cstdlib>
#include <string>
#include <vector>
#include <list>

struct CRule
{   public:
        std::string a;
        std::vector<std::string> b;
        std::string front;
        std::string back;
        CRule():a(""),front(""),back("") {}
        CRule(std::string A,std::string f="",std::string b=""):a(A),front(f),back(b) {}
        CRule(const CRule& r):a(r.a),b(r.b),front(r.front),back(r.back) {}
        CRule& operator>>(std::string s);
        inline void randomize();};

struct CRuleSet
{   private:
        unsigned apply(std::string&,unsigned);
    public:
        std::list<CRule> rs;
        inline void add(CRule);
        void applyrules(std::string&);};

CRule& CRule::operator>>(std::string s) {b.push_back(s); return *this;}

void CRule::randomize() {random_shuffle(b.begin(), b.end());}

void CRuleSet::add(CRule r) {rs.push_back(r);}

void CRuleSet::applyrules(std::string& s) {unsigned x=0;while(x<s.size()) x+=apply(s,x);}

unsigned CRuleSet::apply(std::string& s, unsigned i)
{   for(std::list<CRule>::iterator it = rs.begin(); it!=rs.end();it++)
    {   if ((it->front==""||(i>=it->front.size()&&it->front==s.substr(i-it->front.size(),it->front.size())))&&it->a==s.substr(i,it->a.size())&&(it->back==""||(i<=s.size()-it->back.size()&&it->back==s.substr(i+it->a.size(),it->back.size()))))
        {   it->randomize();
            s.erase(i,it->a.size());
            s.insert(i,it->b[0]);
            return it->b[0].size();}}
    return 1;}

std::ostream& operator<<(std::ostream& os, CRule r)
{
    os << r.front << ((r.front=="" && r.back=="")?"":"<") << r.a << ((r.front=="" && r.back=="")?"":">") << r.back << " -> ";
    if(r.b.size()>1)
    {   os << "{" << r.b[0];
        for(unsigned u = 1; u<r.b.size(); u++) os << ", " << r.b[u];
        os << "}";}
    else if(r.b.size()==1) os << r.b[0];
    return os;
}

std::ostream& operator<<(std::ostream& os, CRuleSet s)
{
    std::list<CRule>::iterator iter;
    for(iter = s.rs.begin(); iter != s.rs.end(); iter++)
        os << *iter << std::endl;
    return os;
}

#endif // GRAFTAL_H_INCLUDED


Please do not steal my code. If you use it, leave the header as it is.
Last edited on
jumper007 (435)
None of us intends to steal anything. We just want to understand it.
Kyon (912)
I know that, but I just want to make sure. ;) The code is really just a framework for creating text-based graftals (or L-systems), shown in the Wikipedia link I posted. With that in mind, the code should be a lot easier to understand.

Hm. Darn. I was close with my formula, but there's still a few flaws (I just tried to reproduce Cn in Excel, but it didn't work). I'll fix it soon, but I'll be off now.

EDIT:
The formula for all combinations is (indexed with n) is:
Cn = 2*Wn + 2*Bn + Rn

In which Wn, Bn and Rn 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).

I made the mistake in the next step, the right answers were:
After looking at the results, you'll find that Bn = Wn+1 and that Rn=Rn-1*2 when n is odd and Rn=Rn-1+Rn-2 when n is even. The starting values are R1=1 and R2=2.

Cn = 2*(Wn + Wn+1) + Rn

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


I'll post the excel document with the calculations tomorrow, I'm really off now.
Last edited on
ne555 (10692)
Just to simplify it a little
R_n = 2*B_{n-1}
W_n = B_{n-1}

R_n = 2*W_n
Kyon (912)
The promised excel document:
http://depositfiles.com/files/85sjy53qe
Topic archived. No new replies allowed.