ZIO17004 - Editorial

mazumder7 · January 4, 2020, 7:41pm

PROBLEM LINK:

ZIO 2017 Problem 4

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 A^k in B for all k ≥ 1.
So to proceed we need to first find the maximum possible value of k for A^k to be a subsequence in B.
Then the answer is total number of good subsequences = number of subsequences as A + number of subsequences as A² + number of subsequences as A³ +…+ number of subsequences as A^k = 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’)
0(‘_’)	1	0	0	0	0	0
1(‘0’)	1	1	0	0	0	0
2(‘0’)	1	2	1	0	0	0
3(‘1’)	1	2	1	1	0	0
4(‘0’)	1	3	3	1	0	0
5(‘0’)	1	4	6	1	0	0
6(‘1’)	1	4	6	7	1	0
7(‘1’)	1	4	6	13	8	0
8(‘0’)	1	4	6	13	8	8
9(‘1’)	1	5	10	23	21	8

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
0(‘_’)	1	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
2(‘1’)	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(‘0’)	1	4	6	2	1	2	1	0	0	0	0	0	0
8(‘0’)	1	5	10	2	1	3	3	0	0	0	0	0	0
9(‘1’)	1	5	10	12	3	3	3	3	0	0	0	0	0
10(‘0’)	1	6	15	12	3	6	6	3	0	0	0	0	0
11(‘1’)	1	6	15	27	15	6	6	9	3	0	0	0	0
12(‘0’)	1	7	21	27	15	21	12	9	3	3	0	0	0
13(‘0’)	1	8	28	27	15	36	33	9	3	6	3	0	0
14(‘1’)	1	8	28	55	42	36	33	42	12	6	3	3	0
15(‘0’)	1	9	36	55	42	78	69	42	12	18	9	3	0
16(‘0’)	1	10	45	55	42	120	147	42	12	30	27	3	0
17(‘1’)	1	10	45	100	97	120	147	189	54	30	27	30	3

Answer = f(17,4)+f(17,8)+f(17,12)+f(17,16) = 97 + 54 + 3 + 0 = 154

techthewalk · June 24, 2022, 5:02am

Hi. I understand it’s an old post, but wanted to provide an alternate solution. I gave the problem to my 9 year old to solve. He, on his own came up with a different solution.
Listing it out here, just for the sake of academics.

1.Capture each element of binary string BINSTR, viz. w= list(BINSTR).
2. Find the length of w{k=Len(w)}
3. Calculate the power set for 2^k involving the indices. Ignore NULL set (no elements) and set containing all the elements, i.e., w.
4. For each set arrived at 3, remove the element represented by the index and check if the resulting string contain ‘0011’ or repeating patterns of ‘0011’.
5. Checks for ‘0011’ pattern is done if the resulting string after removal of index element is divisible by 4.
6. For each success of Step 4, increment the count for possible ways to find a good binary.
7. Return the final count for a given BINSTR.

Example:

BINSTR=‘00111’

w=list(BINSTR)=[0,0,1,1,1]
k=len(w)=5

PowerSet count=2^k=2^5=32

Power Set (involving the indices of the list)={}, {0}, {1}, {2}, {3}, {4}, {0,1}, {0,2}, {0,3}, {0,4}, {1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4}, {0,1,2}, {0,1,3}, {0,1,4}, {0,2,3}, {0,2,4}, {0,3,4}, {1,2,3}, {1,2,4}, {1,3,4}, {2,3,4}, {0,1,2,3}, {0,1,2,4}, {0,1,3,4}, {0,2,3,4}, {1,2,3,4}, {0,1,2,3,4}

Ignore {} and {0,1,2,3,4}: As these will mean dropping NOTHING or the WHOLE String.

Remove element from BINSTR as per the indices given in the Power set calculated.
Hence, remove 0th element for {0}, 1st element for {1} … 1st & 2nd element for {1,2} … 2nd,3rd & 4th element for {2,3,4}…and so on.

For each such removal, check for pattern of ‘0011’ in the modified string.
Viz., for set {1,2}, modified BINSTR would be ‘011’, after removing 0 at index 1 and 1 at index 2. Clearly this does not generate a good binary and hence count is not affected.

Count is affected in {2}, {3}, {4}, where in the element 1 is removed for each of these indices. Hence for the given BINSTR, the value of count is 3, which is the number of ways a good binary can be created from ‘00111’.

It has been tested with the given binary string inside the problem and comes out to be fine. Any loophole(s) may please be communicated. It will help my son to think better.

Thanks and Regards.