PROBLEM LINK:
Editorialist: Rohit Mazumder
PREREQUISITES:
Basic Dynamic Programming
PROBLEM:
A binary string is considered as ‘Good’ when the pattern 0011 is concatenated k times (k≥1). Given a binary string B, find the number of ‘Good’ subsequences present in the string B. A subsequence is formed by dropping some characters from the initial string and keeping
the relative order of the remaining characters same.
EXPLANATION:
Let m = Length of String B,
n = Length of String A.
Let f(m,n) be the number of times the string A occurs as a subsequence in String B.
Case 1:
Consider the following example:
B = 001001101
A = 0011
Note that a subsequences ‘0011’ in string B can be formed by appending a ‘1’ at the end of each of the subsequences ‘001’ in the string ‘00100110’.
So, if the last character of both the strings are the same, we can match them and move on to calculate for the rest of string B and string A, i.e. calculate f(m-1, n-1).
We can also ignore the last character of string B (i.e. delete it!) and search for the subsequence A in the rest of the string B, i.e, we can recur for f(m-1, n).
So, the number of subsequence ‘0011’ present in the substring ‘00100110’(here we have ignored the last character of B) = f(m-1,n)
Hence, the last characters being the same, we get,
The total number of subsequences of the string ‘0011’ in B = f(m ,n) = f(m-1, n-1) + f(m-1, n)
Case 2:
If the last characters of string A and B are different, we can ignore the last character of B and proceed to calculate the number of subsequence of A in the remaining portion of the string B i.e, recur for f(m-1,n)
Combining both the cases, the final recurrences for this problem is:
f(m,n) = f(m-1,n-1) + f(m-1,n); Last characters are same
and
f(m,n) = f(m-1, n); Last characters are different
Base Case for the above recurrence:
f(m, 0) = 1 ; Since the number of empty subsequence in a given string is 1 (for m ≥ 0)
f(0, n) = 0 ; Number of subsequences of A in an empty string is 0 (for n ≥ 1)
Now in this question we have been asked to calculate the value of f for Ak in B for all k ≥ 1.
So to proceed we need to first find the maximum possible value of k for Ak to be a subsequence in B.
Then the answer is total number of good subsequences = number of subsequences as A + number of subsequences as A2 + number of subsequences as A3 +…+ number of subsequences as Ak = f(m, 4) + f(m,8) + f(m,12) + f(m,16) + ….+f(m,4k)
Subtask 1:
B = 001001101; m = 9
Since m = 9, the maximum length of a good subsequence in B is 8 and k = 2.
i.e, the longest possible good subsequence in B is 00110011;
So, A = 00110011; n = 8, k=2
Step 1: Fill in the base cases
0(‘_’) | 1(‘0’) | 2(‘0’) | 3(‘1’) | 4(‘1’) | 5(‘0’) | 6(‘0’) | 7(‘1’) | 8(‘1’) | |
---|---|---|---|---|---|---|---|---|---|
0(‘_’) | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
1(‘0’) | 1 | ||||||||
2(‘0’) | 1 | ||||||||
3(‘1’) | 1 | ||||||||
4(‘0’) | 1 | ||||||||
5(‘0’) | 1 | ||||||||
6(‘1’) | 1 | ||||||||
7(‘1’) | 1 | ||||||||
8(‘0’) | 1 | ||||||||
9(‘1’) | 1 |
Step 2: Fill according the recurrence derived
0(‘_’) | 1(‘0’) | 2(‘0’) | 3(‘1’) | 4(‘1’) | 5(‘0’) | 6(‘0’) | 7(‘1’) | 8(‘1’) | |
---|---|---|---|---|---|---|---|---|---|
0(‘_’) | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
1(‘0’) | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
2(‘0’) | 1 | 2 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
3(‘1’) | 1 | 2 | 1 | 1 | 0 | 0 | 0 | 0 | 0 |
4(‘0’) | 1 | 3 | 3 | 1 | 0 | 0 | 0 | 0 | 0 |
5(‘0’) | 1 | 4 | 6 | 1 | 0 | 0 | 0 | 0 | 0 |
6(‘1’) | 1 | 4 | 6 | 7 | 1 | 0 | 0 | 0 | 0 |
7(‘1’) | 1 | 4 | 6 | 13 | 8 | 0 | 0 | 0 | 0 |
8(‘0’) | 1 | 4 | 6 | 13 | 8 | 8 | 0 | 0 | 0 |
9(‘1’) | 1 | 5 | 10 | 23 | 21 | 8 | 0 | 0 | 0 |
Step 3:
Answer = Number of subsequences ‘0011’ + Number of subsequences ‘00110011’
= f(9,4)+f(9,8) = 21 + 0 = 21
Subtask 2:
B = 100110101010011
A = 001100110011
0(‘_’) | 1(‘0’) | 2(‘0’) | 3(‘1’) | 4(‘1’) | 5(‘0’) | 6(‘0’) | 7(‘1’) | 8(‘1’) | 9(‘0’) | 10(‘0’) | 11(‘1’) | 12(‘1’) | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0(‘_’) | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
1(‘1’) | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
2(‘0’) | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
3(‘0’) | 1 | 2 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
4(‘1’) | 1 | 2 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
5(‘1’) | 1 | 2 | 1 | 2 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
6(‘0’) | 1 | 3 | 3 | 2 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
7(‘1’) | 1 | 3 | 3 | 5 | 3 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
8(‘0’) | 1 | 4 | 6 | 5 | 3 | 4 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
9(‘1’) | 1 | 4 | 6 | 11 | 8 | 4 | 1 | 1 | 0 | 0 | 0 | 0 | 0 |
10(‘0’) | 1 | 5 | 10 | 11 | 8 | 12 | 5 | 1 | 0 | 0 | 0 | 0 | 0 |
11(‘1’) | 1 | 5 | 10 | 21 | 19 | 12 | 5 | 6 | 1 | 0 | 0 | 0 | 0 |
12(‘0’) | 1 | 6 | 15 | 21 | 19 | 31 | 17 | 6 | 1 | 1 | 0 | 0 | 0 |
13(‘0’) | 1 | 7 | 21 | 21 | 19 | 50 | 48 | 6 | 1 | 2 | 1 | 0 | 0 |
14(‘1’) | 1 | 7 | 21 | 42 | 40 | 50 | 48 | 54 | 7 | 2 | 1 | 1 | 0 |
15(‘1’) | 1 | 7 | 21 | 63 | 82 | 50 | 48 | 102 | 61 | 2 | 1 | 2 | 1 |
Answer = f(15,4) + f(15, 8) + f(15, 12) = 82 + 61 + 1 = 144
Subtask 3 :
B = 01011000101001001
A = 0011001100110011
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0(‘_’) | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
1(‘0’) | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
2(‘1’) | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
3(‘0’) | 1 | 2 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
4(‘1’) | 1 | 2 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
5(‘1’) | 1 | 2 | 1 | 2 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
6(‘0’) | 1 | 3 | 3 | 2 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
7(‘0’) | 1 | 4 | 6 | 2 | 1 | 2 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
8(‘0’) | 1 | 5 | 10 | 2 | 1 | 3 | 3 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
9(‘1’) | 1 | 5 | 10 | 12 | 3 | 3 | 3 | 3 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
10(‘0’) | 1 | 6 | 15 | 12 | 3 | 6 | 6 | 3 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
11(‘1’) | 1 | 6 | 15 | 27 | 15 | 6 | 6 | 9 | 3 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
12(‘0’) | 1 | 7 | 21 | 27 | 15 | 21 | 12 | 9 | 3 | 3 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
13(‘0’) | 1 | 8 | 28 | 27 | 15 | 36 | 33 | 9 | 3 | 6 | 3 | 0 | 0 | 0 | 0 | 0 | 0 |
14(‘1’) | 1 | 8 | 28 | 55 | 42 | 36 | 33 | 42 | 12 | 6 | 3 | 3 | 0 | 0 | 0 | 0 | 0 |
15(‘0’) | 1 | 9 | 36 | 55 | 42 | 78 | 69 | 42 | 12 | 18 | 9 | 3 | 0 | 0 | 0 | 0 | 0 |
16(‘0’) | 1 | 10 | 45 | 55 | 42 | 120 | 147 | 42 | 12 | 30 | 27 | 3 | 0 | 0 | 0 | 0 | 0 |
17(‘1’) | 1 | 10 | 45 | 100 | 97 | 120 | 147 | 189 | 54 | 30 | 27 | 30 | 3 | 0 | 0 | 0 | 0 |
Answer = f(17,4)+f(17,8)+f(17,12)+f(17,16) = 97 + 54 + 3 + 0 = 154