### PROBLEM LINK:

#### Author:

Eklavya Sharma

#### Tester:

Hasil Sharma

#### DIFFICULTY:

MEDIUM

#### PREREQUISITES:

Math, Binary exponentiation, Matrices

#### PROBLEM:

A well of depth h initially has 1 cat at the bottom. Each day, every cat splits into 2 cats. One of them moves 1 unit down if it is not at the bottom and the other moves 1 unit up. If a cat reaches the top, it leaves the well. After d days, how many cats are seen leaving the well?

#### QUICK EXPLANATION:

Let V(d) be a column matrix denoting the number of cats at each height in the well on the dth day. So V(0)=[1,0,0,…,0]. Given V(d), we can find V(d+1). We can define a matrix A such that

V(d+1) = A * V(d)

Then V(d) = A^d * V(0)

#### EXPLANATION:

First consider the trivial case when h=1.

Everyday, a cat will divide into 2, one will remain in the well and the other will leave. So, we will see exactly 1 cat leaving the well everyday. However, when d=0, we won’t see any cat coming out of the well today as the cat has just fallen inside and is yet to divide.

So, answer is 0 when d=0, otherwise it is 1.

Now consider the case when h>=2:

Let f(x,d) be the number of cats at height x (from well’s base, 0<=x<=h) after d days.

Initially there is just one cat at the bottom. So,

f(0,0)=1

f(x,0)=0 where 0<x<=h

On other days (i.e. d>=1) we have these relations:

All cats at the bottom were either already at the bottom, or they have come from 1 unit upwell

f(0,d+1) = f(0,d) + f(1,d)

All cats at the top have come from 1 unit downwell

f(h,d+1) = f(h-1,d)

All cats 1 unit below the top are those who climbed up 1 unit yesterday. Note that no cats will roll down from the top, since they left the well on reaching the top.

f(h-1,d+1) = f(h-2,d)

All cats have come from 1 unit upwell or downwell

f(x,d+1) = f(x-1,d) + f(x+1,d) where 1<=x<h-1

Let V(d) be a column matrix containing the number of cats at each height. More specifically,

V(d)=[f(0,d); f(1,d); …; f(h,d)]

So V(0)=[1,0,…,0]

As a day will pass, B(d) will change and this transition can be represented by the matrix A, which can be computed using the recursive equations given above.

B(d+1) = A * B(d)

For example, for h=4, A =

[0,1,0,0,0]

[0,0,1,0,0]

[0,1,0,1,0]

[0,0,1,0,1]

[0,0,0,1,1]

B(d) = A^d * B(0)

The answer to this problem is B(d)[0], which is equal to (A^d)[0][h].

A^d can be calculated in O(log(d)) time by using binary exponentiation.

Remember to use modular arithmetic when multiplying matrices.

#### Time complexity:

O(h^3*log(d))