×

# MCO16202 - Editorial

Author: Zi Song Yeoh

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:

6★zscoder
62813
accept rate: 6%

19.6k349497539

 1 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 -https://www.codechef.com/viewsolution/15122646 Give a Thumbs up, If you like my solution :) answered 26 Aug '17, 21:25 602●1●5 accept rate: 8%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,130
×3,616
×1,965
×2

question asked: 19 Dec '16, 09:54

question was seen: 748 times

last updated: 26 Aug '17, 21:25