Programming Competition problem

[R0mai]

aha, I see, if I understand correctly your first solution didn't thought about the possibility like :

 _______ _________ _ _ _ _
|       |                /
|_______|___       ...   \
|   |       |            /
|___|_______|_____ _ _ _ \

Also does G(0) exist?

Maybe
G(N) = 2G(N-1)+3G(N-2)+2G(N-3)+3G(N-4)... until N is 1 (or 0)?

[tition]

Well, as you correctly pointed out, my first solution (the complicated one) is not very good/practical. However, it accounts for all possibilities, including the one you typed above (which was omitted by my second simple but false "solution").

I still think it doable by hand...

***

Maybe
G(N) = 2G(N-1)+3G(N-2)+2G(N-3)+3G(N-4)... until N is 1 (or 0)?

Umm, can you justify that? The idea seems very good, but to make sure its correct, you should write more details.

You can always define G(0) as to make your formulas true :). There is also a strong mathematical reason for you to justify defining G(0) (which is a separate topic on its own).

[R0mai]

I drew down every possible solution for N=3, and I got 22. Which means we have
G(3) = 2G(2)+3G(1)+2G(0) = 2*7+3*2+2*1 = 22.

The two solutions you were missing was

 _______ ___
|       |   |
|_______|___| 
|   |       |
|___|_______|

and it's mirror.

The special cases which we have to add always are the ones which looks like house's brick structure:

 _______ ___ ___ _______
|       |       |       |
|_______|_______|___ ___|   ...
|   |       |       |
|___|_______|_______|

These are the only ones which haven't been covered in one of our solutions and these. The number of ways we can make these brick-like formations are 2,3,2,3...

Thus :
G(4) = 2G(3)+3G(2)+2G(1)+3G(0) = 2*22+3*7+2*2+3*1 = 72.
G(5) = 2G(4)+3G(3)+2G(2)+3G(1)+2G(0) = 2*72+3*22+2*7+3*2+2*1 = 232.

I hope this solution is good :)

[tition]

What about such combinations, do you account them?

________ _______
|       |   |   |
|_______|___|   |
|   |       |   |
|___|_______|___|

[R0mai]

Yes, these are accounted :

________ _______
|       |   |   |
|_______|___|   |
|   |       |   |
|___|_______|___|

________________
|   |       |   |
|___|_______|   |
|       |   |   |
|_______|___|___| 

This is the case where there are 2 combinations.

And this is with 3 combinations

_____________________
|   |       |   |   |
|___|_______|___|   |
|       |       |   |
|_______|_______|___|

_____________________
|       |       |   |
|_______|_______|   |
|   |       |   |   |
|___|_______|___|___|

_____________________
|       |       |   |
|_______|_______|   |*********
|       |       |   |
|_______|_______|___|

Although, just as I think about it, the last formation has been already checked with G(N-2). (This is G(N-4) which I drew up)

so...

Our function might change to
G(N) = 2G(N-1)+3G(N-2)+2G(N-3)+2G(N-4)+2G(N-5)...

[tition]

[Edit: read the bottom first:)]
It is beginning to get too complicated. You can try to make something like this. Denote by H(N) the function that gives you the partitions of something of the shape

**** ...
 ***...

where the main block is of length N, and there is an extra "ear" sticking out of size 1x1. Then we can compute the functions G and H simultaneously:

G(N)= 2G(N-1)+G(N-2)+2H(N-2)
H(N)=G(N)+H(N-1)

Motivation for the first relation. If your block starts with : or | you get the summand 2G(N-1). Otherwise your block must start with a horizontal slab _ or -. The option that you have two horizontal slabs = is accounted by G(N-2). The other two options are to have something like

________ 
|       |  
|_______|
|   |
|___|

or with the longer slab on the bottom. Those are accounted for by the summand 2H(N-2).

Motivation for the second relation. There are only two options for the "ear": either it is taken by a one by one block, which accounts for the G(N-1) summand, or it is taken by a 2x1 horizontal block, which accounts for the second summand H(N-1).

[Edit:] I just figured out that when I plug in my function H(N-2) back into the first I get exactly your algebgraic relation! It is, in fact, the answer! Now it is clear how to end up this sum: H(0) is well defined, it is the number of ways to split a 1x1 block, which is exactly 1. Therefore, your sum should end like this:

G(N) = 2G(N-1)+3G(N-2)+2G(N-3)+2G(N-4)+2G(N-5)+...+2G(1)+2H(0)=
     = 2G(N-1)+3G(N-2)+2G(N-3)+2G(N-4)+2G(N-5)+...+2G(1)+2G(0)
 

since we already decided to define G(0)=H(0) to be 1 >:)

[tition]

Just an evil algebraic trick came to mind:

Take the "R0mai" relation G(N) = 2G(N-1)+3G(N-2)+2G(N-3)+2G(N-4)+2G(N-5)... and add G(N-3) to both sides. Thus
G(N) +G(N-3) = 2G(N-1)+ G(N-2)+[2G(N-2)+3G(N-3)+2G(N-4)+...]
Now note that the thing in the [] brackets is exactly G(N-1). Therefore
G(N)+G(N-3)=2G(N-1)+G(N-2)+G(N-1)
Finally,
G(N)=3G(N-1)+G(N-2)-G(N-3).

Now, that should be very quick to compute :)). Again, there is a standard way to do it in closed form, google "linear recurrence relation".

[R0mai]

Wow, we solved it !
Thanks for your help :)

Anybody who feels himself at home in mathematics, check if this is the correct format to write down this function with mathematical notation.
The LaTeX editor : http://www.numberempire.com/texequationeditor/equationeditor.php
The code :

G(N)=\begin{cases}
 0& \text{ if } N<0 \\
 1& \text{ if } N=0  \\ 
 2G(N-1)+3G(N-2)+\sum_{i=3}^{N}2G(N-i)& \text{ otherwise }  
\end{cases}

EDIT: Just saw, it could get much more simpler.

[tition]

Cheers to that ! Thanks for the topic & solution :)

[R0mai]

This "evil algebraic trick" is really brilliant :D
tition : does your work involve any mathematics? You seem to know this stuff very well.

[tition]

I am a graduate student in mathematics, math is both my hobby and my profession :) I do lots of C++ these days though (needed for my algebra phd project). This forum is one of the best sources of C++ knowledge and advice. Are you a high school student or in university? Do you plan on doing computer science/math?

[R0mai]

I'm a high school student and I'm gonna matriculate in 2011. I'm planning to continue my studying in math+programming (It is called programmer mathematician (in direct translation) in Hungary).

[R0mai]

I have the official solutions for the problem :
Unfortunately it doesn't include the method for solving it, just the final numbers :
G(2)=7
G(3)=22
G(4)=71
G(5)=228 //G(6) wasn't a question
G(7)=2356
G(8)=7573

using our solution : G(N)=3G(N-1)+G(N-2)-G(N-3)

G(0)=1
G(1)=2
G(2)=7
G(3)=3G(2)+G(1)-G(0) = 3*7+2-1 = 22
G(4)=3G(3)+G(2)-G(1) = 3*22+7-2 = 71
G(5)=3G(4)+G(3)-G(2) = 3*71+22-7 = 228
G(6)=3G(5)+G(4)-G(3) = 3*228+71-22 = 733
G(7)=3G(6)+G(5)-G(4) = 3*733+228-71 = 2356
G(8)=3G(7)+G(6)-G(5) = 3*2356+733-228 = 7573

So our solution is officially correct, yupee :)

[firedraco]

Hm, so I was on the right track with 3G(N-1) at least...These kinds of problems are always fun to do :)