COMPEXP - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest

Author: Utkarsh Saxena
Testers: Jakub Safin
Editorialist: Praveen Dhinwa

DIFFICULTY:

easy-medium

PREREQUISITES:

probability, expected value

PROBLEM:

Consider a string s = “aaabbaa”. Let us call maximal sequence of continuous ones as a group. You have to find expected the number of groups in a string of length N and alphabet size K. The final output required in the problem was twice of this value.

SOLUTION

Satyaki’s solution.

Let E(N, K) be the answer for given N and K.

The recurrence is -

E(1, K) = 1

We can keep the N-th character same as N-1-th character with probability \frac{1}{K}, in this case, the E(N, K) remains same as of E(N-1, K). In the other case when the N-th character is different than the N-1-th character, the number of groups will be 1 more.

E(N, K) = \frac{1}{K} E(N-1, K) \, + \, (1 - \frac{1}{K}) (1 + E(N-1, K))
= E(N-1, K) + (1 - \frac{1}{K})
= E(1, K) + (1 - \frac{1}{K}) * (N-1)
= N - \frac{N-1}{K}

Linearty of expectation based solution

The number of maximal groups is 1 + the number of character changes. The probability of each of change is \frac{K-1}{K}. By linearity of expectation, the number of groups will be (N-1) \frac{K-1}{K}.

So, the answer will be 1 + (N-1) \frac{K-1}{K}.

Combintorics based solution

The number of strings for which the number of groups is g is given by K * (K - 1)^{g - 1} * \binom{N - 1}{g - 1}. The combination \binom{N - 1}{g - 1} denotes the selection of g-1 places where the character will change. The character of the first group can be selected in K ways, then the second group in K-1 ways, third K-1 ways, and so on till the g-th group.

So, the expected number of groups will be

\sum\limits_{g = 1}^{N} {g \cdot \frac{K * (K - 1)^{g - 1} * \binom{N - 1}{g - 1}}{K^N}}
\frac{1}{K^{N-1}} \sum\limits_{g = 1}^{N} {g * (K - 1)^{g - 1} * \binom{N - 1}{g - 1}}

By change of variable g \rightarrow g + 1

\frac{1}{K^{N-1}} \sum\limits_{g = 0}^{N - 1} {(g + 1) * (K - 1)^{g} * \binom{N - 1}{g}}

The term

\sum\limits_{g = 0}^{N - 1} {(g + 1) * (K - 1)^{g} * \binom{N - 1}{g}} = \sum\limits_{g = 0}^{N - 1} {g * (K - 1)^{g} * \binom{N - 1}{g}} + \sum\limits_{g = 0}^{N - 1} {(K - 1)^{g} * \binom{N - 1}{g}}

Binomial theorem states

(1 + x)^n = \sum\limits_{r = 0}^{n} \binom{n}{r} x^r

In this formula, if we replace x by K-1, and n by N-1, we get the second term of the above summation. So, the second term becomes K^{N-1}.

Let us see how to calculate the first term.
By differentiating the binomial theorem by both the sides, we get.

n (1 + x)^{n-1} = \sum\limits_{r = 1}^{n} \binom{n}{r} r x^{r-1}

Multiplying both the sides by x, we get

n x (1 + x)^{n-1} = \sum\limits_{r = 1}^{n} \binom{n}{r} r x^r
n x (1 + x)^{n-1} = \sum\limits_{r = 0}^{n} \binom{n}{r} r x^r

So, by replacing x with K-1 and n by N-1 again, we get the first term of the summation

(N-1) \cdot (K-1) \cdot K^{N-2}

So, the expected number of groups turn out to be

1 + (N - 1) \frac{K-1}{K}

.

Setters and Tester Solution Codes

Setter’s solution
Tester’s solution

4 Likes