PROBLEM LINK:
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
V
_{0} denote the number of substrings00
 Let
V
_{1} denote the number of substrings11
 Let
X = {X
_{1}, X
_{2}... X
_{p}}
denote the length of runs of0
s  Let
Y = {Y
_{1}, Y
_{2}... Y
_{q}}
denote the length of runs of1
s
So, for a string 0011100101100

V
_{0} =3

V
_{1} =3

X
={2, 2, 1, 2}

Y
={3, 1, 2}
Now, a string is valid if and only if
V
_{0} = V
_{1}
You can see that

V
_{0} = ∑_{i=1 to p}(X
_{i} 1)

V
_{1} = ∑_{i=1 to q}(Y
_{i} 1)
Since, number of xx
substrings in a run of x
s of length L
is L1
.
Also, the above expression for V
_{0}, and V
_{1} can be simplified to

V
_{0} =(
∑_{i=1 to p}X
_{i})
X

V
_{1} =(
∑_{i=1 to p}Y
_{i})
Y
Now,
∑_{i=1 to p} X
_{i} is simply the number of 0
s and
∑_{i=1 to q} Y
_{i} is the number of 1
s.
Let

N
_{0} denote the number of0
s 
N
_{1} denote the number of1
s
The necessary and sufficient condition for a string to be a valid is
N
_{0}  X
= N
_{1}  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
N
_{0} = N
_{1}
Since,
N
= N
_{0} + N
_{1}
N
must be even. Thus all strings that are valid, that start in 0
and end in 1
must have the same number of 0
s and 1
s  and, this is necessary and sufficient for such strings to be valid. The number of such strings is
^{N2} 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 N2
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 0
s should be equal to number of 1
s 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
N
_{0} = N
_{1} + 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
^{N2} C
_{((N1)/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(
^{N2} C
_{(N/2)  1} )
, for even N
2(
^{N2} C
_{((N1)/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(k1)
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).