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

×

WTCH - Editorial

PROBLEM LINK:

Practice
Contest

Author: Michael Nematollahi
Tester: Teja Vardhan Reddy
Editorialist: Michael Nematollahi

PREREQUISITES:

NONE

PROBLEM:

You're given a string consisting of characters '0' and '1'. Initially, no two '1's are adjacent. You should output the maximum number of '0's that can be flipped to '1' without having any two '1's adjacent.

QUICK EXPLANATION:

For each maximal substring consisting of only '0's, find out its contribution to the answer.

EXPLANATION:

First, let's answer the first subtask.
If we have $x$ '0's in a row, the maximum number of them that can be flipped to '1' is $\lceil \frac{x}{2} \rceil$. The reason is that if you group the first 2 positions together, the second 2 positions together and so on, you can flip at most one position in each group to '1'. This bound can be achieved by flipping the odd positions (1, 3, 5, ...).

Now let's get back to the original problem. Consider the maximal substrings of the given string that consist of only '0's. For example, if the input string is "0101000", these maximal substrings are "0", "0" and "000". It's easy to see that we can solve the problem for these substrings independently and sum the results.
Let's solve the problem for one of these substrings, $t$. If there is a '1' immediately to the left of $t$, the first character of $t$ is useless and cannot be flipped. Similarly, if there is a '1' to the right of $t$, the last character of $t$ is useless and can't be flipped. Hence, we can reduce $t$'s length appropriately depending on what's to its left and right. What remains is a string consisting of only '0's each of whose characters can be flipped. This is the same as the first subtask, and we already know how to solve it.
So we solve the problem for each of the maximal substrings and sum the results to find the answer to the original problem.

This solution runs in $O(N)$. Refer to the setter's solution to see the implementation.

AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution can be found here.
Tester's solution can be found here.

This question is marked "community wiki".

asked 23 Jan, 23:51

watcher's gravatar image

7★watcher
37
accept rate: 0%

edited 27 Jan, 20:34

admin's gravatar image

0★admin ♦♦
19.8k350498541


Video Editorial : https://youtu.be/10s1prwvfBo

link

answered 27 Jan, 21:31

ivabby's gravatar image

3★ivabby
11
accept rate: 0%

Sir, according to what I did for case 2 where string is a combination of 0s and 1s : first counting number of '1's in the string then we can also consider suppose taking all n digits to be 0 , then applying case 1 formula i.e. n/2 or n/2 +1,, and after that subtracting the count from n/2 or n/2 + 1 that difference will be the output Is this logic wrong?? Plz reply

link

answered 27 Jan, 23:44

ani95's gravatar image

1★ani95
1
accept rate: 0%

@ani95 That approach would not be correct. Consider the input "010010", for which there are two 1's and n = 6. Then n/2 = 3, and your approach would yield 1. However, the correct answer is 0, as no zeros can be flipped given this configuration.

link

answered 28 Jan, 06:48

adavis444's gravatar image

4★adavis444
121
accept rate: 0%

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,875
×850
×39

question asked: 23 Jan, 23:51

question was seen: 1,286 times

last updated: 28 Jan, 06:48