Problem Link:
Difficulty:
Simple
Pre-requisites:
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 1-bits in (M modulo 1000000007) is G.
Quick Explanation:
Let f(n) := number of ways of climbing a staircase of n stairs.
Now, at the last step, you either have climbed 2 stairs or 1 stair. These 2 ways of climbing your last step define two totally different ways of climbing the staircase.
For the first case, there are f(n-2) ways of reaching the n-2’th stair, and for the second case, there are f(n-1) ways of reaching the n-1’th stair.
Hence, f(n) = f(n-1) + f(n-2).
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:
precompute
F[i] = (F[i-1] + F[i-2]) % 1000000007;
this takes O(N) time.
Now, for each test-case, you are given N and G; check if (number of 1-bits in F[N]) == G. If yes, then print “CORRECT”, else print “INCORRECT”. This is then O(1) per test-case.
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
We need to find (f(N) MOD). One may have the doubt as to whether (f(N) MOD) = ((f(N-1) MOD) + (f(N-2) MOD)) MOD. This is in fact true, since (a + b) = (a x) + (b x) (mod x). [In this last equation, I am using "" as in the remainder operator, and “mod” in the sense of number-theoretic modulo relation]
Detailed Explanation:
By looking at the 1st few cases, we see that:
f(1) = 1
f(2) = 2
f(3) = 3
f(4) = 5
f(5) = 8
The analysis of these cases is, in theory, enough for most contestants to deduce the formula mentioned in the Quick Explanation: f(n) = f(n-1) + f(n-2)
The main problem, is how can we compute it fast enough, as for N = 5000, using the recursive formula as given above
int f(int n)
return (f(n-1) + f(n-2)) % 1000000007;
will always be too slow (in fact, program will never terminate in useful time).
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 N-th 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:
|f(N+1)| = MATRIX * | f(N) | = MATRIX^(N-1) * |f(2)|
| f(N) | |f(N-1)| |f(1)|
As we want the vector on the right-hand side to remain the same for any N, we see that we will need to raise our MATRIX to the power of N-1.
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(N-1) = f(N+1)
Similarly, for the second row, we see that:
1* f(N) + 0 * f(N-1) = f(N)
So, the required matrix is:
|1 1|
|1 0|
So, our final relationship in matrix form is:
|f(N+1)| = |1 1|^(N-1) * |f(2)|
| f(N) | |1 0| |f(1)|
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^(N-1) in O(log N) time. This is matrix exponentiation.
Having done this, we can find the number of 1-bits in the number M with the function
ONES(int n)
ans = 0
while n > 0 do
if n%2 == 1
ans = ans + 1
n = n/2
return ans
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
