ZIO16001 - Editorial

Editorialist: Ayush Kapadia

Prequisite : Basic Recursion Concepts

Problem Link:

Short Description: Count number of binary strings of length n having “11011” as substring.

Explanation :

There are basically 2 major ways to solve this type of problem. They are :
(1) By actually generating the string character by character from an empty string keeping all contraints in mind.
(2) By iterating over all possible strings and count only those that satisfies our constraints.

The second method takes huge amount of time. For example in case of n = 9, you will have to check 512 string which is tedious for pen and paper based exam (However this approach is feasible to solve using computer)

So let us discuss first approach in detail with this question in mind. Later you can apply this technique to other questions also.

Generator Method :

Overview :
In this method we start generating the string character by character. It is recursive type of algorithm. First we look at the choices for first character. Based on that we will recursively call the function for size less than that given in problem. For example suppose problem asks to count number of English letter words having character 'A' in the word. So for this problem we can have 26 choices for first letter. If we choose 'A' as our first letter , then for rest of letters we can put anything we want , so if first letter is 'A', then count is 26^(n-1). However if first letter is not 'A' , then ofcourse there has to be 'A' in remaning (n-1) letters. So the problem becomes same for size (n-1). Thus recursion equation becomes f(n) = (1)*(26\wedge(n-1)) + (25)*(f(n-1)).

There actually arises three cases at every point.
Case – 1) Constraints already satisfied (i.e Substring already formed from characters we generated) Answer is total possible strings you can form from remaining characters
Case – 2) Not a single part of constarint satisfied (i.e. our substring cannot start from any of characters we generated till now). Answer is F(remaning characters)
Case – 3) Partial constarint is specified (i.e substring can start from characters generated uptill now)
Answer is either solve subcases or make a seperate generator function so that you can recurse for similiar contraints for lower problem size.

So for any problem of this type, we have to first found some recursive equations based on cases described above. And then use your understanding for getting the answer through recursion equation.

Solution to our problem

We have to generate binary string of length n. So let us generate that.

Case 0: First digit is 0

Then substring “11011” definitely cannot start at first digit. So substring has to be found in remaining (n-1) binary digits. So problem basically reduces to counting number of strings of length n-1. So for this case it is F(n-1)

Case 1: First digit is 1

Case 1.1 : Second digit is 0
 Then the same conclusion. Substring cannot start at 0th digit as well as 1st digit. So problem    reduces to counting number of strings of length n-2 .  F(n-2)

Case 1.2 : Second digit is 1
We will be using special generator function for this subcase (for counting strings with first two digits as “11”. ) The reason you will soon understand.  G(n)

Lets call our special generator function be G(n) and our original function be F(n).

So F(n) = F(n-1) + F(n-2) + G(n)

So if we know G(n) and all previous values of F(n) then it is very easy to calculate F(n). But the question is how to calculate G(n)

So lets generate G(n)

Case 0: Third digit is 1
Now the problem arises, substring can still start at second digit or third digit. So we cannot ignore that. So now what to do. Think deep. The problem is nothing again but the same G function with length n – 1. This because now you have “111” as start . Ofcourse you know substring cannot start at 1st digit. But it can start at 2nd or third digit. This is same as G(n-1) (You have to generate string of length n-1 with start as “11” ). (Remember first digit is of no use in this case) G(n-1)

Case 1 : Third digit is 0

Case 1.1 : Fourth digit is 0
So now you have “1100” at start. Ofcourse you cannot have substring at 1st,2nd , 3rd or 4th digit. So problem basically reduces to counting number of strings of length n-4.  F(n-4)

Case 1.2 : Fourth digit is 1
     
     Case 1.2.1 : Fifth digit is 0
     So now you have “11010” at start. Ofcourse you cannot have substring at 1st,2nd , 3rd or 4th  or 5th digit. So problem basically reduces to counting number of strings of length n-5. F(n-5)

     Case 1.2.2 : Fifth digit is1
     So you have found the substring. So remaning can be anything. So 2^(n-5)

So G(n) = G(n-1) + F(n-4) + F(n-5) + 2\wedge (n-5)

Thus knowing function F and G values at previous points, you can easily calculate it.

So final equation becomes :

F(n) = F(n-1) + F(n-2) + G(n)
G(n) = G(n-1) + F(n-4) + F(n-5) + 2\wedge(n-5)

You can easily solve this using recursion.

Base Case : F(5) = 1 and G(5) =1
F(n) = G(n) = 0 , for n<5

For your reference here is the table you will get :

n | \;F(n) \;\;G(n)
------------------
5 | \;\:\;\;\; 1 \;\;\;\;\;\;\;1
6 | \;\;\;\;\; 4 \;\;\;\;\;\;\;3
7 | \;\;\;\;\;12 \;\;\;\;\;7
8 | \;\;\;\;\;31 \;\;\;\;\;15
9 | \;\;\;\;\;75 \;\;\;\;\;32
10 | \;\;\;175 \;\;\;\;69
11 | \;\;\;399 \;\;\;\;149

I believe that only few of the editorials for ZIO questions are actually good,
All of them have mainly given us solutions that cannot really be used for solving using a pen and paper in the actual exam

Please tell me whether the method I use is good. :pray:

Question:
Count number of binary strings of length n having 11011 as substring.

Reference:
ZIO 2016 (Problem 1)

For n=9:
We will list out all the possible valid binary strings.

Case 1: 11011xxxx
Case 2: x11011xxx
Case 3: xx11011xx
Case 4: xxx11011x
Case 5: xxxx11011

Here, x denotes 0 or 1.

So the number of all combinations will be:
5\times2^4=5\times16=80

But, here we observe that there are instances where the same combination occurs in more than one case.

We will subtract such instances from the total (80) as follows:

Case 1: 11011xxxx
Case 4: xxx11011x
2 intersections

Case 2: x11011xxx
Case 5: xxxx11011
2 intersections

Case 1: 11011xxxx
Case 5: xxxx11011
1 intersection

Therefore,
80-5=\boxed{75}

Similarly we compute for n=10 and n=11:

For n=10:

Case 1: 11011xxxxx
Case 2: x11011xxxx
Case 3: xx11011xxx
Case 4: xxx11011xx
Case 5: xxxx11011x
Case 6: xxxxx11011

So the number of all combinations will be:
6\times2^5=6\times32=192

Case 1: 11011xxxxx
Case 4: xxx11011xx
4 intersections

Case 2: x11011xxxx
Case 5: xxxx11011x
4 intersections

Case 3: xx11011xxx
Case 6: xxxxx11011
4 intersections

Case 1: 11011xxxxx
Case 5: xxxx11011x
2 intersections

Case 2: x11011xxxx
Case 6: xxxxx11011
2 intersections

Case 1: 11011xxxxx
Case 6: xxxxx11011
1 intersection

Total intersections:
4\times3+2\times2+1=17

192-17=\boxed{175}

For n=11:

Case 1: 11011xxxxxx
Case 2: x11011xxxxx
Case 3: xx11011xxxx
Case 4: xxx11011xxx
Case 5: xxxx11011xx
Case 6: xxxxx11011x
Case 7: xxxxxx11011

Combinations: 7\times2^6=7\times64=448

Cases with number of intersections = 8
1 and 4
2 and 5
3 and 6
4 and 7

Cases with number of intersections = 4
1 and 5
2 and 6
3 and 7

Cases with number of intersections = 2
1 and 6
2 and 7

Cases with number of intersections = 1
1 and 7
Actually there are two intersections.
But, comparing with Case 4, we find one of the possibilities has already been covered.
Case 1: 11011xxxxxx
Case 7: xxxxxx11011
Case 4: xxx11011xxx

Total intersections:
8(4)+4(3)+2(2)+1(1)=49

448-49=\boxed{399}

What do you think of this method?

6 Likes

better and more realistic than the one in the editorial(One that can actually be used to solve during the paper).

btw I solved it using the same method.

1 Like