CLMBSTRS - Editorial

clmbstrs
combinatorics
editorial
feb13
simple

#1

Problem Link:

Practice

Contest

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


#2

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.


#3

@kuruma (Bruno) Great question brother.

I am amazed on how you managed to transform the simple and innocent Fibonacci sequence into this wonderful question!

Hats off!


#4

@tijoforyou,

I am very happy that people liked my question, that many people solved it and that 72 people recommended it on FB… :smiley:

Unfortunately, my knowledge on algorithms is not very advanced yet, so I basically, play and attempt to write interesting questions with what I know :slight_smile:

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


#5

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 :slight_smile:


#6

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 :slight_smile:


#7

@rajorshi
check ur code for overflow…
“fk=f1+f2;”.It should be"fk=(f1+f2)%MOD;"


#8

ca anyone tell me what is wrong with my approach … http://www.codechef.com/viewsolution/3648881


#9

Well written :slight_smile:


#10

And N was small too. :slight_smile:


#11

:slight_smile: Looking forward to more results from your “plays”


#12

Variables a, b, c, d should be of 64-bit integer type.
In your solution products like d*(b + a) is calculated incorrectly due to overflow of 32-bit integer type.

Simply fixing this leads to AC:
http://www.codechef.com/viewsolution/1834364


#13

@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 !


#14

Refer to tester’s solution for implementation :slight_smile:


#15

You must compute your fib number modulo MOD