CODIGO 2K20, need help in CHEF AND TILING

I was unable to solve this during the contest.
Acc. to me , the recurrence formula should be…

Tn+2 = Tn+1.T1 + 2.Tn
and T1 = 2
and T2 = 6
I checked some solutions they use something like Fibonacci Logn method to generate the answer but I don’t get it . Please help and how can I solve these type of questions in Logn when I have recurrence formula.

1 Like

The Linear recurrence relation formed is a(n) = 2a(n-1)+2a(n-2) which is as good as -
2*(a(n-1)+a(n-2)).
The above equation is for 2*(Fibonacci sequence).
And for calculating nth fibonacci number efficiently -
For proof of nth fibonacci number using matrix exponentiation -

And finally here you go by just replacing 2 (where to replace is left for readers :wink: :wink:) in the matrix for getting your nth modified fibonacci sequence.

3 Likes

I drive This recurrence too, but took me to try different cases to figure it out.
How do you drive this recurrence?
what is the intution behind it?

I also went through different values for n and found the recurrence relation.
But , for a good explanation -

1 Like

You have tiles of length 1 and 2 only of colours Blue AND RED
To fill length n from (n-1) length there are two ways Blue and Red tiles of length 1
To fill length n from (n-2) length there are two ways Blue and Red tiles of length 2

nice thanks ,it has good explanation

Ohhh…great I didn’t put the value of T1 in the relation, everything was in front of me.
Thank you for the explanation bro

1 Like

@adikr_singh gave the correct explanation of how i think about this recurrence

1 Like

I still did not get why everyone creates the initial matrix of [[2, 2],[1, 0]] but not of [[2, 1],[1, 0]] ?

1 Like

@chaudhary_19 Go through this blog and comment section down there:-
https://codeforces.com/blog/entry/14516

In Fibonacci , we use [[1, 1],[1, 0]] but here everyone uses [[2, 2], [1, 0]]
I want to know why? can you please explain that part

1 Like


Refer to this

1 Like

Thank you @everule1 , finally i got how the matrix is formed from the recurrence relation

1 Like