SPIT2-Editorial

general
, ,
1

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;
}
2

Could you explain why this recurrence is true?

3

@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 :slight_smile: