Solution to Ladder by codility

9 Mar


Question Name: Ladder

To solve this question, there are two key points. Firstly, for a given N rungs, the number of different ways of climbing is the (N+1)th element in the Fibonacci numbers. Naturally, we could get the following answer. It works well. BUT the detected time complexity is O(L**2). What!!! How could it be?!

So you need to know the second key to achieve 100/100 solution: how to do modulo computation in an optimized manner.

Yes, the detected time complexity is O(L) now.

UPDATE – 12/27/2014: thanks to @Martin. The old solution cannot pass the new test cases. We need to improve the performance again! In Python, the interger could be as large as the memory can hold. Therefore, we do not need to handle with the overflow issue. But at the same time, the big interger is kind of resource-consuming, for both time and space. To achieve a better performance, we need to avoid the big integers when we are computing the fib numbers. Actually, we do not need the full-bit fib number, because only some tailing bits are used in the final result.

34 thoughts on “Solution to Ladder by codility

  1. what if A[i]=4 and B[i]=1? Then the way to cal modulo is wrong . But your solution can pass all the test cases. I’m confused about it.
    Could you explain to me why whis case would not happen ?

  2. I am not sure that this solution would work for C++. By problem formulation: the number of steps in ladder can be as much as 30000. So to calculate and keep Fibonacci numbers in array will not be possible as it is done in the example above (line:9-10). It will overflow long-long data type. I guess that the whole buzz about modulo operation. It offered in order to avoid this problem.Fortunately, it can be proved that recurrence Fn=Fn-1+Fn-2 works also under module transformation at any step. That can be used inside the loop to keep Fn manageable. However, since modulo 2^p can be different for any number in array A[i], we have to calculate several times and that increase complexity. We cannot create one static lookup Fibonacci array.
    I am not sure about Python, but I have doubts that it can keep array of Fibonacci without overflowing up to 30000 elements? (the unknown to me test case bundle may not check that situation)

    • Awesome analysis! Actually you are right. We should do the modulo operation while computing the Fibonacci numbers in the line #8.

      In Python, the range of intergers is unlimited, or say only limited by the memory size. So the Python code could pass the test.

      • This won’t work as values of A[i] are not ascending. In other words, you need either to store or map all of the used fibonacci numbers that you used, or to calculate them at each iteration.

        However, there is a way to optimize your algorithm.

        I’ve done it with java.

        The idea is to calculate only the needed fibonacci numbers, and map them.
        You are calculating fibonacci numbers for all the range (for all the possible values of fibonacci until the LIMIT or the size of A), while in reality, you only need that number of values in the worst cast scenario (that they exist in the input).

        in other words: the size of array A, could be 30000. but values could be of the range [1,10]. In your code, to solve the problem, you are calculating fibonacci numbers for 30000.

        Now for the C++ version, a dynamic array could be allocated, or a linked list, of a custom class, where long long ( or 2 integers ) can be used (why not?) (in this case, functions for adding should be implemented to cover the overflow) (or covering only the first 8 bits of the integer is sufficient) Notice that B[i] is of the range: [1,30], this means that the problem by definition, and Sheng’s solution needs a representation on no more than 30 bits (less than an integer). It can be easily proven that the upper part of the long long is not needed and we only need to AND the lower part with the B calculation that Sheng suggested.

        Another suggestion for C++ is to do binary sum.
        something like: (a+b) & 255

        I know that there isn’t much difference between O(N) and O(3N) but I think O(N) that I have is still better than O(3N) above.

        However, here’s my 100/100 solution in java

        • First of all, thank you for the awesome discussion.

          I did use the cache to store all the value of fib, in fib = [0] * (limit+2). It stores all the value from fib(0) to the up bound (fib(L+1)). Therefore, I do not need to consider whether A[i] is or is not ascending.

          Finally, I did used the bitwise operation in my final solution.

  3. Hello, Sorry i might be asking very naive question. But i didn’t understand the logic that one could ascend to Nth rung by Fibonacci(N+1) ways.
    I could notice it by examples but i don’t exactly understand the logic.
    Could someone please help me understand the same.

    • Let the f(x) be the number of different ways to achieve the step x.

      To achieve step x, you could
      either jump from x – 1 by one rung
      or jump from x – 2 by two rungs

      Therefore f(x) = f(x – 1) + f(x – 2).

  4. I used almost the same method as your first solution except declare an empty list instead of a fixed size list ( i.e. result = [] instead of result = [0] * len(A) ). It got 100/100 score and the time complexity is O(L).

    Probably the huge size of array declaration leads to timeout I guess.

    • Also in Python? IMO, allocation memory in batch, like [0] * len(A), should be more efficient than dynamically increasing it.

  5. Hi, I hope this is still working….I’m trying to understand what the ladder problem is asking…I don’t understand basically what I have to return..I see the example and according what I think module is it doesn’t make any sense…I guess it is because I wrong about what a module is…but according to the first post, I read this ” If A[i]=4 and B[i]=1, we need the result as Fibonacci_number(4+1) % (2^1)” It’s what I understand that the problem is asking and for me module(%) is for example is a divide 3 by 2 I get 1,5 the module for me is 5….well knowing that the vector example that is returned in the ladder example doesn’t match with this definition….I use C++ and % is module and It’s what I believe you suggested but I must have not understood anything……thanks!!!

  6. I didn’t expect there were these much discussion for this one. Is it all about the reminder of Fibonacci numbers that is sufficient to meet the need of possible 2 to the power of N (N<=30)?

    In order to meet O(L) time complexity, each calculation must be finished in O(1), which will require some memorization up front. However, it's not possible to calculate Fibonacci(30000) without the help of some BigInteger implementation. Luckily, Codility only asks the reminder of some 2^N. So, we only need to store the reminder of any Fibonacci using 2^L as the divisor. This will make sure we have all bits necessary to do any modulo of 2^p, given p in vector B.

  7. Hi, found the solution in ruby 100/100

  8. Would it be better to calculate the Fibonacci numbers using the formula in a lambda?
    fib = lambda x: int(( pow((1+sqrt(5))/2,x) – pow((1-sqrt(5))/2,x))/sqrt(5))

Leave a Reply

Your email address will not be published. Required fields are marked *