Need help for algorithm in combination problem

[Maggi Iggam]

Here's the complete problem
[ http://www.iarcs.org.in/inoi/contests/apr2006/Advanced-1.php ]

Problem is that i don't have any idea how would i calculate number of possible tilings ? I do know bit of introductory combinatorics and permutation combination but here i am completly stuck . Second problem is limit for n is too large - 10^6 , so answer can be too too large , printing last 4 digit is no problem though we could print it using mod but computing number of possible tilings is giving me trouble !

[ne555]

With combinatorics there are two issue: (a)
- Make sure to count them all
- Don't repeat elements

Considering your problem:
Let's define a `perfect tiling' as the one that does not have a vertical division.
So in a 2x2 room = is a perfect tiling but || is not.

Now if you want to tile a room of 2xn you could do a perfect tiling, or do a perfect tiling to the left and decorate the right as you please
That gives the formula N(K) = P(K) + \sum_{J=1}^{K-1} P(J) N(K-J)
show that it respects (a)

[Maggi Iggam]

Umm... maybe its correct but i really couldn't understand it @ne555 .

i didn't get what 'vertical division' meant - is it a vertical 2 'I' shaped tile you mean ?

I also couldn't get the meanings of variables you used to calculate that formulae.

Could you please elaborate a bit more ?
And thanks for replying :)

[ne555]

With vertical division I mean a vertical line of length 2. As if you took a handsaw and cut the floor.
So in a 2x1 the `perfect tiling' will be a vertical bar
2x2, two horizontal bars
2x3, there are two ways, both with the L shape.

N() is the number of possible tilings
P() is the number of perfect tilings
2xK is the dimension of the room
J just an iterator

[Maggi Iggam]

Okay , i understood whole of your last post , but your first post formula is still mystery to me , i still can't understand what those notations mean a '\' before sum , what sum_{J=1}^{k-1} meaned and what was k .

And also it would be very helpful your formulae for some small input - like for 2x3 , number of possible tiling is 5 as shown in example of link .
& Thankyou before hand :D

[ne555]

It's the sum symbol. From J=1 to K-1
N(3) = P(3) + ( P(1) N(2) + P(2) N(1) )
N(3) = 2 + ( 1 * 2 + 1 * 1 ) = 2 + ( 2 + 1 ) = 5

[Maggi Iggam]

Okay , i understood all of these but have little problem in calculating that P() part .

How do we calculate P(a) ???

Thanks for this formula it looks like some magic , i tried with N(1),N(2) - it works !!!

From defination of P()

Let's define a `perfect tiling' as the one that does not have a vertical division.

shouldn't P(1) be 0 as it has only 1 possible tiling that is with 1 vertical '|'

[ne555]

I mean a division in the middle. Of course it would end (and start) with a vertical line.

[Maggi Iggam]

Okay , but still How do we calculate perfect tiling p(a) ???

[mik2718]

After calculating N(3) you know all these
N(3),N(2),N(1),P(3),P(2),P(1)

so now you need N(4) which is

N(4) = P(4)+( P(1)N(3)+P(2)N(2)+P(3)N(1) )

you know all of these except P(4). I am guessing that P(k) is always 2 (L shaped piece at each end and rectangular ones layed like bricks inbetween)

So this gives you all you need for N(4), and you can continue this way.

[Maggi Iggam]

Okay , let me try P(k)=2 @mik2718 , but i don't think it should be always 2 , else @ne555 would have not put P(n) in formula and instead put 2 in place of P(k) !

[Maggi Iggam]

I don't think it is working true @mik2718 .
Where are you @ne555 ? please help man :/

[ne555]

I am guessing that P(k) is always 2 (L shaped piece at each end and rectangular ones layed like bricks inbetween)

Yep, except for k=1, and k=2 were P(k) = 1

¿how is it not working? Make sure that
- It's count them all
- don't repeat elements

The algorithm should be O(n)

[Maggi Iggam]

Yeah , i think its my mistake , the concept seems easy a bit now but its getting more & more tricky to implement the simple concept , this erroneous code is not giving the required output :(

#include<iostream>
using namespace std;
int valueofp(int a) {if (a==1 || a==2) return 1; else return 2;}
int main() {
    int i,n[1000]={0,1,2},p,sum=0,k;
    cin>>k;
    sum=valueofp(k);
    for (i=1;i<k;i++) {
        sum+=valueofp(i)*n[k-i];
    }
    cout<<sum;
    system("PAUSE");
}

[ne555]

¿What values does the `n' array hold?
Also, you didn't do the mod part.

[Maggi Iggam]

'n' array is used to store all previous n(k) . Yeah i didn't did mod part , i will add that later but before it i put input as 13 and it prints wrong answer as given in example of question ! Thats why i left that mod part for debugging purpose :)

[ne555]

> 'n' array is used to store all previous n(k)
¿where?

[Maggi Iggam]

Well , i exactly didn't get what you meant by 'where' .
But obviously n[k] will store n(k) , n[k+1] stores n(k+1) and so on and first three , ie k=1,2,3 are exception to that p(k)=2 so i have initialized these exception as n[0]=0,n[1]=1,n[2]=2 .

[ne555]

where do you assign anything to n

[Maggi Iggam]

Yeah you are correct @ne555 . I have already tried many variations , and i am trying more so dont think that i have left this question :) If still i wont be able to get this simple implementation , i will let you know , thankyou once again