BINSUBS - Binary Subsequence - Editorial and Video explanation

editorial
1

Hello everyone,
So I hope that you are clear with the problem statement and if not then here’s the link to the problem:-

Binary Subsequence | CodeChef

So there are few possible cases:-

  1. All zeros in the string
  2. All ones in the string
  3. A mix of both (definitely first 2 cases can be considered as the specialization of this case)

Now there’s one small observation and it is the fact that to have a sequence which is non-decreasing there’s always a transition from 0 to 1 at some point (If there are 0s and 1s in the string).

Suppose, we have a string 01001011, now there are various such transition possible from index 0 to 1, 1 to 2 and so on… But for every transition boundary we must make sure that there is no ‘1’ on the left side of the current transitional boundary and no ‘0’ on the right. So to make this sure we are required to erase those 1s and 0s that are on left and right respectively. Number of deletions is our cost.

So in order to solve this problem:-

  1. Count all 0s and 1s

  2. Initially ans = min(0s, 1s)

  3. We will keep moving to the right and if current cost is less it is our new answer.

That’s it…

Here’s the video solution:-

Here’s the solution:-
Solution: 42184692 | CodeChef

1 Like