UVa : 12041 (BFS (Binary Fibonacci String))



// link: http://uva.onlinejudge.org/external/120/12041.html
// Runtime: 0.080s
// Tag: Recursive, Dp

/*
 * File:   main.cpp
 * Author: shahab
 *
 * Created on August 5, 2011, 8:58 PM
*/

#include <cstdlib>
#include <cstdio>
#include <string>
#include <iostream>

using namespace std;

long long fibo [50];
string bfs [50];

void generateFibo ()
{
    fibo [0] = 1;
    fibo [1] = 1;

    for ( int i = 2; i <= 50; i++ ) fibo [i] = fibo [i - 1] + fibo [i - 2];
}

int bfsOfPosition (int n, long long pos)
{
    if ( n < 31 ) return bfs [n] [pos] - '0';

    if ( pos < fibo [n - 2] ) return bfsOfPosition (n - 2, pos);
    else return bfsOfPosition (n - 1, pos - fibo [n - 2]);

}

void generateBfs ()
{
    bfs [0] = "0";
    bfs [1] = "1";

    for ( int i = 2; i < 31; i++ ) bfs [i] = bfs [i - 2] + bfs [i - 1];
}

int main(int argc, char** argv)
{
    generateFibo ();
    generateBfs ();

    int testCase; scanf ("%d", &testCase);

    while ( testCase-- ) {
        long long n, start, end; scanf ("%lld %lld %lld", &n, &start, &end);

        if ( n > 48 ) {
            n = n % 2 ? 47 : 48;
        }

        if ( n < 31 )
            for ( long long i = start; i <= end; i++ ) printf ("%c", bfs [n] [i]);
        else
            for ( long long i = start; i <= end; i++ ) printf ("%d", bfsOfPosition (n, i));

        printf ("\n");
    }

    return 0;
}

2 thoughts on “UVa : 12041 (BFS (Binary Fibonacci String))

  1. @Niteesh Mehra
    There are 2 gotchas here
    1. bfs string position query wont exceed 2^31. (i, j < 2^31 – 1)

    for example,
    50th bfs = 48th bfs + 49th bfs
    that means, 1st portion of 50th bfs is exactly same as 48th bfs
    so, if 48th bfs length exceeds 2^31 then you don't need to find 50th bfs
    you can tell the answer of any question on 50th bfs using 48th bfs

    so its enough to create upto 48th bfs … but that will exceed time and space complexity
    thats why, i created upto 30 bfs, which is feasible in terms of space & time complexity

    now we need to think about 31th to 48th bfs

    2. query won't exceed 10000. ( j – i <= 10000 )
    so i ran a recursive function here, which returns 0 / 1
    bfsOfPosition (int n, long long pos)
    that is, nth bfs contains 0 or 1 in the pos-th position

    if ( n < 31 ) i’ve already calculated it, so just return the result

    otherwise
    we need to determine, pos-th character of nth bfs whether comes from (n-2)th bfs or (n-1)th bfs

    for example, we want to find the 250th character of 14th bfs
    14th bfs length = 377
    13th bfs length = 233
    12th bfs length = 144

    as we know 14th bfs = 12th bfs + 13th bfs
    so 250th character of 14th bfs definitely not in 12th bfs
    250th character of 14th bfs is same as -> (250 – 133)th character of 13th bfs

    hope it helps 🙂
    my solution is not a good dp .. but its similar to a dp solution 😛

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s