You are not logged in. Please login at www.codechef.com to post your questions!

×

MCO16202 - Editorial

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:

asked 19 Dec '16, 09:54

zscoder's gravatar image

6★zscoder
62813
accept rate: 6%

edited 13 Jan '17, 15:19

admin's gravatar image

0★admin ♦♦
19.6k349497539


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 :)

link

answered 26 Aug '17, 21:25

rohan_bose95's gravatar image

5★rohan_bose95
60215
accept rate: 8%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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