post  Programming Competition problem

R0mai (196)   Link to this post
Hi guys,

Today was the national student competition's for high school students programming category in Hungary. There was a problem which I couldn't solve. This round was a paper round, we weren't allowed to use anything.
Here is the problem :
We have a 2*N sized pavement. We can cover this with 1*1 and 1*2 sized pieces. How many ways can we do it if N=2, N=3, N=4, N=5, N=6, N=7, N=8.
Example for N=3 :
1
2
3
4
5
 
 __________
|      |   |
|______|___|
|   |      |
|___|______|


Can anybody solve it? :)
firedraco (2048)   Link to this post
Is stuff like:


11 2
3 44
 and

1 22
33 4

different?
R0mai (196)   Link to this post
Yep, for N=2 the solution is 7.
firedraco (2048)   Link to this post
Hm, then what I would do is start with 1s in all spots, and then go through and replace each one with a 2x1 block, and sort of keep doing that (I hope that's clear). Then, do it for N=2,N=3, maybe N=4, and try to find a formula for it.

Oh and also, does stuff like:


1 2 3
1 2 3 work?

Random Guess: (2^[N+1])-1
Last edited on
R0mai (196)   Link to this post
Yes you can rotate the 2*1 pieces.
If I remember correctly, I got 21 for N=3, I tried drawing down every position. I don't know if it's the correct answer, they haven't published the solutions yet.
firedraco (2048)   Link to this post
Hm, just had an idea. Couldn't you get the answer for N=2, then N=3 do something like this:


N2 N
N2 3

And since there are 3 ways to do the N3, then N=3 is at least 3*(N=2 answer). There will be other answers since you can make 2*1s extend into the N2 area[1], but you can get a lower bound.

[1] Which would be 3*(N=1) I think.
Last edited on
chrisname (1342)   Link to this post
Hungary

You're Hungarian? Hm, your English is good.
R0mai (196)   Link to this post
You're Hungarian? Hm, your English is good.


Thanks :)
Bazzy (3164)   Link to this post
Do you name your variables using the Hungarian notation?
I always wanted to ask such a stupid question
R0mai (196)   Link to this post
Do you name your variables using the Hungarian notation?

No, and we are not constantly hungry eiher :).
chrisname (1342)   Link to this post
we are not constantly hungry eiher :).

Lol...
Last edited on
PanGalactic (369)   Link to this post
No, and we are not constantly hungry eiher :).


Well, there goes that theory.
tition (238)   Link to this post
Well, there are two distinct cases:
Either
1. you have some place in your arrangement a 2x1 block standing up vertically (left-right side of length 2, top bottom side of length one)
or
2. you have no 2x1 block standing up.

Let us think for a while on case 1. If you have a block "standing up" at position k, it splits the picture in two parts, say something like *****|** (the vertical line represents position k, in this case this is position 6). Then the number of ways to make a partition is equal to the number of ways to solve your problem for a (2 x K-1) block times the number of ways to do it for a (2 x (N-K) ) block.

Now, suppose you have solved the problem for an 2 x M block in case you never have a vertical 2x1 block. Call that function int AnswerNoVertical2by1blocks(int length). Then the function you are looking for can be given as:

1
2
3
4
5
6
7
8
9
 
int FinalAnswer(int StartingIndexOfBlock, int EndingIndexOfBlock)
{ int result=0;
  // in the below, the index int i represents the SMALLEST index for which 
  // you have a vertical 2 by 1 block
  for(int i=StartingIndexOfBlock;i<=EndingIndexOfBlock;i++)
  { result+=AnswerNoVertical2by1blocks(i-StartingIndexOfBlock)*FinalAnswer(i+1,EndingIndexOfBlock);
  }
  return result;
}
Last edited on
tition (238)   Link to this post
Now, how do we find the function int AnswerNoVertical2by1blocks(int length) ?

Since we cannot put vertical block, it is the same as splitting one horizontal stripe of height 1 squared.

In how many ways can we split a horizontal stripe of length int length? This is a trick from the math competitions arsenal: the answer is a Fibonacci number. Let us see why:

Suppose the number of ways to split a horizontal stripe 1xN is F(N). We have two options for the left-most block: it is either 2x1 or 1x1. Therefore:
  
F(N)=F(N-1)+F(N-2)

which is exactly how you define Fibonacci numbers. Note F(1)=1, F(2)=2.
Therefore:
1
2
3
4
 
int AnswerNoVertical2by1blocks(int length)
{ int n=Fibonacci(length);
  return n*n;
}

And finally,

1
2
3
4
5
6
7
8
9
10
 
int Fibonacci(int N)
{int fib_small=1;
  int fib_large=1;
  for (int i=1;i<N;i++)
  { int temp= fib_large;
    fib_large+=fib_small;
    fib_small=temp;
  }
  return fib_large;
}
tition (238)   Link to this post
It might be possible to solve this problem in a "closed" form modulo some reasonable combinatorial functions, but hey, why should we when we have computers :)

Cheers!
R0mai (196)   Link to this post
tition :

This was a paper round, we didn't have computers. We didn't had to write a program (not even in pseudo code) which solves the problem.
The problem should be possible to solve without any help (even without a pocket-calculator), on paper.
tition (238)   Link to this post
Well, up to the 8th (shifted) Fibonacci number:

F(1)=1
F(2)=2
F(3)=3
F(4)=5
F(5)=8
F(6)=13
F(7)=21
F(8)=34

Once you know FinalAnswer(1), you easily get FinalAnswer(2), and so on. The program above is very easy to carry out by hand.
tition (238)   Link to this post
I jost woke up and an "easier" solution came to my mind, perhaps it was even the solution you were expected to give.

Let the way to pave a 2xN block be denoted by G(N). Then

[Edit:] Just found the below is wrong.
G(N)= 2G(N-1)+3G(N-2).

There is a way to solve such "recurrence relations" directly, in "closed form", see http://en.wikipedia.org/wiki/Recurrence_relation . But, just for fun, let us do it by hand :)

To explain why G(N)= 2G(N-1)+3G(N-2), just note that either the first 2 x 1 block is like this | or like this :, which is two combinations, so G(N)=2G(N-1)+..., but you also have the option for starting with a horizontal 2x1 block, like this _ or like this -, or with a two lying horizontal blocks =, which accounts for the coefficient 3.

[Edit:] Or you can start with ._ on the bottom and - on the top. Which makes the above simple "solution" wrong. A famoust quote (heard it attributed to Einstein): One should make matters as simple as possible, but never simpler!

Therefore
1
2
3
4
5
6
7
8
9
 
G(0)=1
G(1)=2
G(2)=7
G(3)=2*7+3*2      = 14+(7-1)= 14+6= 20
G(4)=2*20+3*7     = 40+(20+1)     = 61
G(5)=2*61+3*20    = 122+(61-1)    = 182
G(6)=2*182+3*61   = 364+(182+1)   = 547
G(7)=1094+182*3   = 1094+ (547-1) = 1640
G(8)=1650*2+547*3 = 3300+ (1640+1)= 3941


Last edited on
R0mai (196)   Link to this post
wow tition, that's very nice and clean and obvious now.

Thank you for dreaming about this problem :).

I'll let you now when the official evaluating guide comes out.

*Now banging head to the wall...*
tition (238)   Link to this post
oh.. crap... My "solution" is wrong: I edited to indicate where. Well, I should then revert to my first proposal for a solution :((((

Sry for my stupidity!
Last edited on

Pages: [1] [2]


Registered users can post in this forum.