ACMICL2 - Editorial



Eklavya Sharma


Hasil Sharma




Math, Binary exponentiation, Matrices


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?


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)


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(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 =

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: