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))