Couldnt understand the editorial for this question - "Team "

general
1

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.

1 Like
2

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
3

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.

4

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

5

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’