Is the editorial solution to this problem really correct?

I was attempting problem - Binary string construction from the last contest hosted on Hackerearth.

Honestly, I could not understand the editorial solution, partly because the explanation is not descriptive enough as others might agree. Anyways, the point is - Why is the solution correct ?
Any explanation specifically on how they are counting bad strings by creating blocks of 0 would be appreciated.

As far as I understood this way of counting would involve over-counting, as in consider block of 1 : 0001111 [x = 3, y = 4]

this will also appear for block of 2: _00____
Probably, my understanding of the solution is incorrect.

Simply put, their editorial is just very bad.
This is a very well known problem.

Since the proofs are not elaborated enough there, I’ll outline the proof of reflection, which I believe is the simplest.


Let’s start with an up down walk, where 1 means up, and 0 means down. Imagine the x value to be the index, and the y axis is the difference between the no. of 1s and the no. of 0s. It can be seen that a ‘1’ is up, and ‘0’ is down.
This is what they look like

Let’s say a sequence is wrong. That implies that there is at least one point, where y=-1. Let us take it’s earliest instance. There must have been k 1s and k+1\ 0s. That means there are x-k-1\ 0s, and y-k\ 1s left. Let us reflect all the points after this point about the line y=-1. All lines after this would switch, means all the 0s will become 1s, and all the 1s will become 0s. So the y co-ordinate of the end will become -1 + (x-k-1) - (y-k) =x-y-2.

Let us take any sequence of length x+y that ends at x-y-2. Since y\ge x, the lowest point must be \le -2 since that is the maximum value for the ending point. Therefore, there must be some point where y=-1, since we start at y=0. We can reflect all the points after the first instance of y=-1 about the line y=-1. This will give us bad sequence with x 0s and y 1s. Since there will be a y=-1 and the reflection about line y=-1 will make the last point of height y-x, we can conclude this is true.

Since every bad sequence has a unique up down walk that ends at x-y-2 and every up down walk has a bad sequence that has x 0s and y 1s, we can claim that they are equal in number.

To find the number of up down walks that end at x-y-2 and have length x+y, we can simply do \binom{x+y}{x-1}, since it must have x-1 ups and y+1 downs.

Therefore that answer is \binom{x+y}{x} - \binom{x+y}{x-1}.

1 Like