You are not logged in. Please login at www.codechef.com to post your questions!

×

SPIT2-Editorial

PROBLEM LINK

Practice
Contest

Author : Ankit Sagwekar
Tester : Vikesh Tiwari
Editorialist : Ankit Sagwekar

DIFFICULTY

Easy

PREREQUISITES

basics,array,implementation

PROBLEM

Given two integers 'm' and 'n'. Find the number of combinations of bit-size 'n' in which there are no 'm' consecutive '1'.

EXPLANATION

We are given with m and n. There are 3 cases for any given value of n and m

  • Case 1: when n is less than m for this the ans will be equal to ans=pow(2,n).
    eg: 3 2 all the 2 bit words i.e 00 01 10 11 will not have 3 consecutive 1 ,thus all of them are selected.

  • Case 2: when n is equal to m for this the ans will be equal to ans=pow(2,n)-1.
    eg: 3 3 all the 3 bit words i.e 000 001 010 011 100 101 110 111 out of which only one word will have 3 consecutive '1'.

  • Case 3: when n is more than m This test case needs some computation which we will see through eg.
    eg: 3 4
    Here we first calculate for
    m n
    3 3 = 7
    3 2 = 4
    3 1 = 2
    then adding this ,we get for 3 4 as 7+4+2=13.
    here m=3 thus we calculate for 3 values and add them .
    eg:4 6
    here we first calculate for
    m n
    4 5 = 29
    4 4 = 15
    4 3 = 8
    4 2 = 4
    then adding this ,we get for 4 6 as 29+15+8+4=56.
    here m=4 thus we calculated for 4 values and add them .

Note: for faster computation we can precompute all the values and can store them in 2-D matrix.

Complexity:

(O(N^2.logN))

C++ Code

#include <stdio.h>
#include<math.h>
int main(void) {
    // your code goes here
    long long int t,n,m,i,j,k,a[15][105],l;
    scanf("%lld",&t);
    for(i=2;i<=10;i++)
    for(j=1;j<=50;j++)
    {
        if(j<i)
        a[i][j]=pow(2,j);
        else if(j==i)
        a[i][j]=pow(2,j)-1;
        else
        {
            k=i;
            l=j-1;
        while(k>0)
        {   k--;
            a[i][j]+=a[i][l--];
        }
        }
    }
    /*

         for(i=2;i<=10;i++)
    {
    for(j=1;j<=50;j++)
    {
        printf("%lld\t",a[i][j]);
    }
    printf("\n");
    }
         */
         // you can uncomment the above section to see all the precomputed values 
    while(t--)
    {
        scanf("%lld%lld",&m,&n);
        printf("%lld\n",a[m][n]);
    }
    return 0;
}

asked 23 Apr '15, 07:21

vicky002's gravatar image

1★vicky002 ♦♦
2561314
accept rate: 27%

edited 23 Apr '15, 17:22

admin's gravatar image

0★admin ♦♦
19.7k350498541


Could you explain why this recurrence is true?

link

answered 26 Jun '15, 00:29

skybolt's gravatar image

2★skybolt
1
accept rate: 0%

@skybolt :You will find many such recurrence relations in binary manipulations ,only thing you can do is play with them to find some newone's. Still we can prove the recurrence as follows: Consider m=2

Let’s call the function that calculate the number of n-digit binary numbers without two adjacent 1 bits a(n).

Now let’s define two helper functions. a0(n) returns number of those binary numbers that end with zero, and a1(n) returns number of those ending with one. Thus, it’s obvious that:

a(n) = a0(n) + a1(n)

Now, suppose we already have a set of (n-1)-bit numbers generated and now, based on that, we want to generate a new set of n-bit numbers. We’ll do that by adding a single bit to the end of each (n-1)-bit number. Because we care only about adjacent 1s, we can add 0s to the end of every (n-1)-bit number. Thus:

a0(n) = a(n-1)

On the other hand we can’t add 1s to each (n-1)-bit number. We can only add 1 to numbers which had 0 at the end. Thus:

a1(n) = a0(n-1)

By simple substitution we can rewrite the last equation into the following one:

a1(n) = a(n-2)

Get back to the definition of a0(n) and a1(n) and make the final substitution:

a(n) = a(n-1) + a(n-2)

thus we can generalize the above method for m>2 Hope this solves your doubt :)

link

answered 26 Jun '15, 22:35

ankit15's gravatar image

2★ankit15
412
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×3,741
×825
×77

question asked: 23 Apr '15, 07:21

question was seen: 1,037 times

last updated: 26 Jun '15, 22:35