REL202 - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice 
Contest

Author: Divyesh Savaliya 
Editorialist: Divyesh Savaliya

DIFFICULTY:

EASY - MEDIUM

PREREQUISITES:

Math

PROBLEM:

You are given N. You have to count the number of binary strings (consists of only ‘0’ and ‘1’) of length 2*N such that the number of '1’s in first string of length N is double of the number of '1’s in second string of length N. Print the answer modulo 10^9+7.

EXPLANATION:

Lets try to solve this step by step and then sum all the value. Half string means the string of length N.

  1. Find the number of strings which contain two ‘1’ in first half string and one ‘1’ in second half string.

  2. Find the number of strings which contain four ‘1’ in first half string and two ‘1’ in second half string.

  3. Find the number of strings which contain six ‘1’ in first half string and three ‘1’ in second half string.

Do above step upto the number of ‘1’ in first half string become N if N is even or N-1 if N is odd.

Now, how to compute the required number of strings. Simple, just by using Permutation and Combination.

  1. The number of strings which contain two ‘1’ in first half string are nothing but binomialCoeff(N,2).The number of strings which contain one ‘1’ in second half string are nothing but binomialCoeff(N,1). So, the answer for step 1 is binomialCoeff(N,2) * binomialCoeff(N,1).

  2. Similarly, the answer for second step is binomialCoeff(N,4)*binomialCoeff(N,2).

So, the final answer is :

      for(int i=2;i<=N;i=i+2)
             sum = ( sum + ( ( binomialCoeff(N,i) * binomialCoeff(N,i/2) ) % 10^9+7) ) % 10^9+7;

Now, how to compute binomialCoeff(N,r). Since, the value of N <= 1000. You can use Dynamic Programming technique to pre-compute it.

Time complexity is O(N) if we pre-compute binomialCoeff in O(N*N).

AUTHOR’S SOLUTIONS:

Author’s solution can be found here.