# Forum

11.04.2011   # 1
2010 Final Round - FibonacciBits

I noticed that this problem no one had it correctly solved(without timing out). Every solution had arround 80-85/100.

I tried solving it with permutations. Every fibonacci number (there are 7 of them below 31) in its binary representation is permuted and checked if its in the range from Start to End; The number is permutated until it passes End.This approach passed 80/100 (20 timeouts).

So I tried an update by setting the first permutation of every fibonacci number to be the closest one below Start; Again 80/100 (20 timeouts);

Does anyone has any idea on how to correctly solve the problem???

12.04.2011   # 2

15 Timeouts

static int [] fibonacci = {1,2,3,5,8,13,21,34};

public static int modernFibonacci(int S, int E) {
int count=0;
for (int i=S;i<=E;i++) {
int tmp = Integer.bitCount(i);
for (int p=0;p<8;p++) if (fibonacci == tmp) { count++; break; }
}
return count;
}

12.04.2011   # 3

boro most of the solutions used this method and got 15 timeouts. So it's not the right approach for correctly solving the problem

12.04.2011   # 4

The optimal solution uses dynamic programming approach. The complexity is very low O(N*N) where N is the maximal length of the binary string, in our case 32. I wrote similar code in the last year finals, but I had a bug in my code, I didn't find my mistake during the competition...

I think that the code is easily understandable, I also used comments.

``public class FibonacciBits {    // comb[k][j] is the number of binary strings with length i    // which start with bit k (0 or 1) and which have j number of one bits    int comb[][][] = new int[2][40][40];    void fillComb() {        int i,j,k;        // initial values for string length 1        comb[0][1][0] = 1;        comb[0][1][1] = 0;        comb[1][1][0] = 0;        comb[1][1][1] = 1;        for (i=2;i[j] = comb[0][i-1][j]+comb[1][i-1][j];                if (j > 0) {                    comb[1][j] = comb[0][i-1][j-1]+comb[1][i-1][j-1];                }            }        }    }    // calculates the number of binary strings which are less than or equal to num    // and which have number of ones in their binary representation which is    // fibonacci number    int calculate(int num) {        int i,j,k;        int res = 0;        boolean fibonacci[] = new boolean[40];        fibonacci[1] = true;        fibonacci[2] = true;        fibonacci[3] = true;        fibonacci[5] = true;        fibonacci[8] = true;        fibonacci[13] = true;        fibonacci[21] = true;        fibonacci[34] = true;        String s = Integer.toBinaryString(num);        int L = s.length();        // number of "good" numbers with length less than length of num        for (i=1;i[j];                }            }        }        // now we calculate for the number of "good" numbers with        // length equal to length of num        int passed_ones = 1;        int N;                for (i=1;i == true) {                        res += comb[0][N][j];                    }                }                passed_ones++;            }        }                k = Integer.bitCount(num);        if (fibonacci[k] == true) {            res++;        }        return res;    }    public int modernFibonacci(int S, int E) {        int a,b;        fillComb();        if (S == 0) {            a = 0;        } else {            a = calculate(S-1);        }                b = calculate(E);                return b-a;    }}``
12.04.2011   # 5

Parts of some for cycles are missing. I think I have some rough idea of what you are doing with the combinations. Can you repost the code and maybe give an explanation for the filling and calculating part?

13.04.2011   # 6

Sorry. It was not my fault, html does not handle special characters well I guess, because even after change of > and < I couldn't place the code in nice tags Maybe I don't do something right... That is why I place the code here http://pastebin.com/sTL1Pgyz

21.04.2011   # 7

There was a problem with the text editor in the forum. It should be fine now.