LEBINARY - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest

DIFFICULTY

EASY MEDIUM

PREREQUISITES

Math, Big Integer, Binary Search

PROBLEM

How many strings of length N - where each character is 0 or 1 - exist such that number of 00 substrings is equal to 11 substrings. Further, you are given a number of at most 1000 digits and you have to verify if this is the result for some N.

QUICK EXPLANATION

Pre compute the result for all N until number of digits in the answer exceed 1000 digits. Given a number, we can binary search for it in the pre computed table.

EXPLANATION

Any valid string that starts with 0 can be transformed by replacing all 0 with 1 and 1 with 0 to get another valid string. Thus, it is sufficient to calculate the number of strings for an N that start with 0 and multiply the result by 2 - to get the number of valid strings of length N.

For some N

  • Let V0 denote the number of substrings 00
  • Let V1 denote the number of substrings 11
  • Let X = {X1, X2 ... Xp} denote the length of runs of 0s
  • Let Y = {Y1, Y2 ... Yq} denote the length of runs of 1s

So, for a string 0011100101100

  • V0 = 3
  • V1 = 3
  • X = {2, 2, 1, 2}
  • Y = {3, 1, 2}

Now, a string is valid if and only if
V0 = V1

You can see that

  • V0 = ∑i=1 to p (Xi - 1)
  • V1 = ∑i=1 to q (Yi - 1)

Since, number of xx substrings in a run of xs of length L is L-1.
Also, the above expression for V0, and V1 can be simplified to

  • V0 = (∑i=1 to p Xi) - |X|
  • V1 = (∑i=1 to p Yi) - |Y|

Now,
∑i=1 to p Xi is simply the number of 0s and
∑i=1 to q Yi is the number of 1s.

Let

  • N0 denote the number of 0s
  • N1 denote the number of 1s

The necessary and sufficient condition for a string to be a valid is

N0 - |X| = N1 - |Y|

Consider strings that start with 0 and end in 1. It is intuitive to see that in such a string
|X| = |Y| = k

Thus, the necessary and sufficient condition for all strings that start in 0 and end in 1 is
N0 = N1

Since,
N = N0 + N1

N must be even. Thus all strings that are valid, that start in 0 and end in 1 must have the same number of 0s and 1s - and, this is necessary and sufficient for such strings to be valid. The number of such strings is
N-2 C (N/2) - 1
Where N is even.

This result is because first and last digits are fixed and we can only choose (N/2) - 1 digits to be 0 from the remaining N-2 digits. The rest of them are 1.

There cannot be an even length string that starts in 0 and ends in 1 since number of 0s should be equal to number of 1s and odd length strings will contradict that.

Now, consider the case of strings that start in 0 and end in 0.
We will have the following situation
|X| = |Y| + 1 = k + 1

Hence, the necessary and sufficient condition for all strings that start in 0 and end in 0 is
N0 = N1 + 1

We see that N must be odd. Thus all strings that are valid, that start in 0 and end in 0 must have exactly one more 0 than 1 - and , this is necessary and sufficient for such strings to be valid. The number of such strings is
N-2 C ((N-1)/2)
Where N is odd.

We do not consider the case of strings that start in 1 because we have already established by symmetry that all strings that start with 0 can be transformed to obtain strings that start with 1.

Thus, we have the complete function for the number of valid strings
f(N) =
2( N-2 C (N/2) - 1 ), for even N
2( N-2 C ((N-1)/2) ), for odd N

f(2) = 2

Iteratively build the table of pre calculated f values from f(3) to f(t), where f(t) has more than 1000 digits. t will be 3333. By building iteratively it is meant that calculating f(k) is possible from f(k-1) by doing at most one multiplication and one division.

The order of building this table should be O(D*t), where D is the number of digits of precision you store (in this case 1000).

Now, given a number in the input, you can binary search for this number in this table.

SETTERS SOLUTION

Can be found here

TESTERS SOLUTION

Can be found here
The tester uses similar inferences to arrive at the formula. He then goes on and hashes the values instead of storing them and binary searching through them (and hence is a tad bit faster).

6 Likes