PROBLEM LINK:http://www.codechef.com/ICL2015/problems/ACMICL2 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(h1,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(h1,d+1) = f(h2,d) All cats have come from 1 unit upwell or downwell f(x,d+1) = f(x1,d) + f(x+1,d) where 1<=x<h1 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".
asked 24 Mar '15, 23:59
