×

# ACMICL2 - Editorial

http://www.codechef.com/ICL2015/problems/ACMICL2

Eklavya Sharma

Hasil Sharma

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

This question is marked "community wiki".

2★f2012086
15
accept rate: 0%

19.8k350498541

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,875
×2,658
×890
×166
×153
×41
×40

question asked: 24 Mar '15, 23:59

question was seen: 1,038 times

last updated: 23 Apr '15, 17:11