MCO16202 - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest

Author: Zi Song Yeoh

DIFFICULTY:

EASY

PREREQUISITES:

Dynamic Programming

PROBLEM:

Given a binary string with some characters replaced with question marks. Find the number of ways to replace the question marks with 1 or 0 so that the resulting string has exactly k runs for all 1 \le k \le n.

EXPLANATION:

Firstly, the naive solution is to iterate through all possible binary strings and find the number of runs in each of them. This solution will work in O(2^{n} \cdot n) time.

Now, to get a faster solution, we need dynamic programming. Let dp[i][j][k] denote the number of ways to fill the question marks from digits 1 to i so that there are exactly j runs and the i-th digit is k. (so k = 0 or 1)

We can easily update the dp by considering all possible values of the current digit.

If the i-th digit can be 1, then dp[i][j][1] += dp[i - 1][j - 1][0] + dp[i - 1][j][1].

If the i-th digit can be 0, then dp[i][j][0] += dp[i - 1][j - 1][1] + dp[i - 1][j][0].

The time complexity of this solution is O(n^2).

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.

RELATED PROBLEMS:

2

Here is My solution .

I solved it by kind of the same method … but with less computations compared to the Tester’s Solution.

( there was no need to make j < str.size() in the Tester’s solution … j<=i+1 will work as the number of runs cant be greater than the array size taken so far )

Solution Link -CodeChef: Practical coding for everyone

Give a Thumbs up, If you like my solution :slight_smile:

3 Likes