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

×

Couldnt understand the editorial for this question - "Team "

The first 2 cases of Problem C are clear but I am unable to make the head and tail of the last case. Can someone explain it to me ? Or maybe a clear explanation of the total problem would suffice. This is the problem. Thanks in advance.

asked 26 May '17, 12:46

chari407's gravatar image

2★chari407
44827
accept rate: 0%


I too could not make out what the first condition means. But i can explain the test-cases based on second condition.

  • First test case is possible with one '0' and two '1' as it can be represented as '101'
  • Second test case is possible as well with four '0' and eight '1' as it can be represented as '110110110101'
  • Third test case is possible too with four '0' and ten 1 as it can be represented as '11011011011011'
  • However, the last test case is not possible with one '0' and five '1' as there will be at least three '1' together in the row, which violates the second condition. Hence the output -1
link

answered 26 May '17, 14:42

jjtomar's gravatar image

1★jjtomar
15910
accept rate: 4%

Thanks for your effort. But I need the explanation of the last case of the editorial.

(27 May '17, 08:43) chari4072★

As i said, the last case is not possible with one '0' and five '1' as there will at least be three '1' together (the best option is "111011" or "110111") which violates the second condition. That is why the output is '-1'

(27 May '17, 10:14) jjtomar1★

There are two conditions that are mentioned in the problem:
1)There shouldn't be any consecutive 0s.
2)There shouldn't be more than 2 consecutive 1s

You can think of it in this way, since the 0s must not be consecutive, there must be at least a single 1 in between every 0, ie., the valid solution will be of this form:

0 _ 0 _ 0 _ 0....._0 where the "_" represents a gap, that must be filled by 1s and there cannot be more than two 1s in any gap. If there 'n' 0s, then there will be n-1 gaps in between them, and two more gaps at the beginning and the end, so you should have at least n-1 1s (to fill the gaps in between) and at most ((n-1)*2 + 4) 1s (two 1s in every gap in between and two 1s in the beginning and the end).

if you see the last test case, it has one 0 and five 1s. You need to put these five 1s on either side of the single 0 such that no side has more than two 1s, another way to look at this is to take a string with five 1s say "11111", try to put a 0 in this string at any position, you will see that no matter where you put the 0, there will be atleast three consecutive 1s in the resulting string.

link

answered 27 May '17, 11:37

hemanth_1's gravatar image

6★hemanth_1
1.4k11
accept rate: 28%

edited 27 May '17, 11:42

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:

×682

question asked: 26 May '17, 12:46

question was seen: 386 times

last updated: 27 May '17, 11:42