Lesson 11: Ladder (Ladder)

Lesson 11: Ladder
https://codility.com/programmers/lessons/11

This is indeed a problem about Fibonacci numbers.
Let's think of the possible combination from 0 rung and then increase the number of rungs.

Rungs   : Ways
0 rungs : 0 

1 rungs : 1 --> 0

2 rungs : 2 --> 1 --> 0
            |-> 0

3 rungs : 3 --> 2--> 1 --> 0
            |   |-> 0
            |
            --> 1 --> 0

As shown, The number of different ways to climb up the ladder with i rungs is the sum of the ways for the ladders with i - 1 rungs and i - 2 rungs. (Think of this, if we climb up 1 rung, the number of the combination from there is the same as the case with the ladder made of i - 1 rungs. If we climb up 2 rungs, the number of the combination from there is the same at the case with the ladder made of i - 2 rungs. So we only have to simply add these numbers).

Then, if we have the O(L) space, then we can use the O(L) algorithm to compute Fibonacci numbers.

However, Fibonacci numbers can be very big for big L. The problem states that we don't need the actual number. Instead the value must be applied modulo 2^B[i], and Max(B) = 30. So we simply can cut off the upper 2 bits of int, as sizeof(int) for the Codility environment for C programming language is 32 bit. So 30 bit is indeed within this limit. We apply bitwise-and to fibonacci numbers to avoid overflow and since, we can neglect the upper 2 bit, this is fine to answer this problem.

Also don't forget we need to apply module 2^B[i] when we compute the value to be returned.

This strategy gives the 100% score.

#include <alloca.h>

struct Results solution(int A[], int B[], int L) 
{
    //the problem states that B <= 30, which means
    //we only have to consider the_number_of_combination % 2^30. 
    //and the combnation increases like the fibonacci numbers.
    int* fibM = (int*)alloca(sizeof(int) * (L + 1));
    
    fibM[0] = 0;
    fibM[1] = 1;
    fibM[2] = 2;
    
    int i;
    for (i = 3; i <= L; i++){
        //0x 3FFF FFFF = 0B 0011 1111 1111 1111 1111 1111 1111 1111.
        //we cut off the 2 bits from MSB to avoid overflow by applying bitwise-and.
        fibM[i] = (fibM[i - 1] + fibM[i -2]) & 0x3FFFFFFF;
    }

    struct Results result;

    result.C = (int*)malloc(sizeof(int) * L);
    result.L = L;
    
    for (i = 0;  i < L; i++){
        //it may be better to use fibM[A[i]] & ((1 << B[i]) - 1);
        result.C[i] = fibM[A[i]] % (1 << B[i]);
    }
    
    return result;
}