Problem Link:Difficulty:Simple Prerequisites:Combinatorics Problem:Given a staircase of N stairs, in how many different ways can you reach the top, assuming you can climb one or two stairs at a time. Let this number of ways be M. Check if the number of 1bits in (M modulo 1000000007) is G. Quick Explanation:Let f(n) := number of ways of climbing a staircase of n stairs. Hence, f(n) = f(n1) + f(n2). For small n, we have f(1) = 1, f(2) = 2. (This is just the Fibonacci sequence offset by 1). Finally, our algorithm is as follows: Overall time complexity: O(N + T). Note, you can also use matrix exponentiation to get f(n) in O(log(n)) time. But for the constraints n <= 10^6, this is a bit of an overkill. Note on % operator:lets say MOD = 1000000007 Detailed Explanation:By looking at the 1st few cases, we see that: f(1) = 1 The analysis of these cases is, in theory, enough for most contestants to deduce the formula mentioned in the Quick Explanation: f(n) = f(n1) + f(n2) The main problem, is how can we compute it fast enough, as for N = 5000, using the recursive formula as given above
The Matrix Exponentiation Approach:The key idea is that we can use the base cases of the recursion and matrices, to deduce a formula that will allow us to compute the Nth number very fast, as all we need to do is matrix exponentiation. Let's see how: We want to have a relationship that goes like this:
As we want the vector on the righthand side to remain the same for any N, we see that we will need to raise our MATRIX to the power of N1. All that is left now is to assemble the matrix itself. Now, if we use rules of matrix multiplication and if we use the recursive relationship we obtained, we see that 1st row of matrix must be only composed of ones, as: 1 * f(N) + 1 * f(N1) = f(N+1) Similarly, for the second row, we see that: 1* f(N) + 0 * f(N1) = f(N) So, the required matrix is: So, our final relationship in matrix form is:
Using the fact that for a matrix M: M^(2k) = M^k * M^k, and M^(2k+1) = M * (M^k) * (M^k), we can find M^(N1) in O(log N) time. This is matrix exponentiation. Having done this, we can find the number of 1bits in the number M with the function
Having computed the number of ones of the value obtained after matrix exponentiation, all that is left is to compare it with the guess G and print the string “CORRECT” or “INCORRECT” accordingly. The Memoization/DP Approach:This approach was described in Quick Explanation, where you have an array F[] which stores the values of f(n) modulo 1000000007 for you. Instead of calling the function f again and again for values you already know, just compute the values as you go along and use the stored values. Setter's Solution:Can be found here Tester's Solution:Can be found here
This question is marked "community wiki".
asked 12 Feb '13, 18:20

I am very happy that people liked my question, that many people solved it and that 72 people recommended it on FB... :D Unfortunately, my knowledge on algorithms is not very advanced yet, so I basically, play and attempt to write interesting questions with what I know :) All the positive feedback I have received is very valuable to me and I hope I can keep setting problems and help Codechef community as much as it already helped me!! Best regards, Bruno answered 12 Feb '13, 20:48

I found and stored the number of bits itself in each of the Fibonacci numbers (modulo 1000000007). After all, as max T was about N/10, that didn't take much of a time, compared to the total time. answered 12 Feb '13, 20:22

Hi all, Can somebody please explain to me why my answer is not correct (url: http://www.codechef.com/viewsolution/1827874). I have checked others accepted answers and i did try them using test cases that i have made but i wasn't able to see any difference between my solution and others, so i am very confused right now as to what is that i did wrong. Any help will be much appreciated, thanks in advance. N.B: BTW, i did found out that my calculation of the Fibonacci number was an overkill, a simple loop should have worked :) answered 13 Feb '13, 04:06
1
Variables Simply fixing this leads to AC:
(13 Feb '13, 04:12)
1
@anton_lunyov: Thanks for the quick and great response, actually i was thinking that integer overflow truncate when it's set to a variable that can't fit the result, but apparently i was wrong, integer overflow happen in the multiplication (32bits x 32 bits => 32 bits), but it's very weird that in my machine i am getting the same result with your change and without it, maybe it's the compiler that fix this automatically !? i am using btw gcc 4.6.3, weird !
(13 Feb '13, 04:46)

Guys, can someone help me understand why my solution fails? http://www.codechef.com/viewsolution/1819499 Alternatively, it would be great if codechef provides links to actual input file used for evaluation, so that we see where exactly our programs go wrong after the submission! Thanks, [N00b] Raj :) answered 13 Feb '13, 22:58

ca anyone tell me what is wrong with my approach .... http://www.codechef.com/viewsolution/3648881 answered 27 Mar '14, 12:45

Well written :)