CODEWITHSUNDEEP
c++calgorithmmatrixrecurrence
Bruce
Bruce

Reputation: 955

Finding the recurrence relation and matrix exponentiation

I am trying to find the recurrence relation for this problem on Codechef:

http://www.codechef.com/problems/BWALL

I know once I find it, I can easily solve it using matrix exponentiation. But I'm having trouble understanding how it gets the right answer. There is a solution here, but I'd like if someone explained it in a better manner?

enter image description here enter image description here enter image description here

Is there is a simple rule of thumb to find recurrences or something like that? Thanks!

Upvotes: 1

Views: 550

Answers (1)

Dr_Sam
Dr_Sam

Reputation: 1878

The "general rule" to find a recurrence is to understand how is the solution of a problem related to the solutions of smaller problems. But more than that, I don't think that there's a general procedure to find the recurrence.

For this particular example, here is how you can find the recurrence.

Suppose that you have a big wall of size N. Now, just look at the end of the wall. More precisely, from the end of the wall, find the first place with a "vertical separation", i.e. the first place where you can split the wall into two smaller walls without L-shape.

Example:

(A) Here is the wall:

X###X#XXX#X

XX#XX#XXXXX

The splitting with the end gives you:

X###X#XXX #X

XX#XX#XXX XX

(B) Another wall

X###X#XXX

XX#XX#XXX

The splitting with the end gives you:

X###X# XXX

XX#XX# XXX

What is the size of the small piece of wall that you can get between the splitting and the end of the wall? Well, you can have 1, 2 or 3, but not more (otherwise, you could make a smallest splitting).

The possibilities for the small piece are actually the ones given in your question (yes, the 7 small blocks).

So, to build a wall with size N, you must:

  • build a wall of size N-1 and add to end the size-1 small block
  • or build a wall of size N-2 and add to end one of the four size-2 blocks
  • or build a wall of size N-3 and add to end one of the two size-3 blocks.

So, the number T(N) of possible walls with size N is

  • the number of walls with size N-1 (with size-1 block in the end) -> T(N-1)
  • plus the number of walls with size N-2 with 4 possible end blocks (with size 2) -> 4 T(N-2)
  • plus the number of walls with size N-3 with 2 possible end blocks (with size 3) -> 2 T(N-3)

And there you get your recurrence.

Hope it helps!

Upvotes: 1

Related Questions