Post 11.04.2011   # 1
Subject 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???

lazzrov is offline Reply
Post 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;

boro is offline Reply
Post 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

lazzrov is offline Reply
Post 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];

k = Integer.bitCount(num);
if (fibonacci[k] == true) {
return res;
public int modernFibonacci(int S, int E) {
int a,b;
if (S == 0) {
a = 0;
} else {
a = calculate(S-1);

b = calculate(E);

return b-a;

igorkulev is offline Reply
Post 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?  

lazzrov is offline Reply
Post 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

igorkulev is offline Reply
Post 21.04.2011   # 7

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

pstanoev is offline Reply

Please login to post reply.