THEGAME - More Info for the Formula

general
,
1

Could someone elaborate more the formula of E(X)? I mean this was the formula for expected value:

E(000) = 1\cdot\frac{x_0}{x_0 + x_1 + x_2} + 2\cdot(\frac{x_1}{x_0 + x_1 + x_2}\cdot\frac{x_0}{x_0 + x_2} + \frac{x_2}{x_0 + x_1 + x_2}\cdot\frac{x_0}{x_0 + x_1}) + 3\cdot(\frac{x_1}{x_0 + x_1 + x_2}\cdot\frac{x_2}{x_0 + x_2}\cdot\frac{x_0}{x_0} + \frac{x_2}{x_0 + x_1 + x_2}\cdot\frac{x_1}{x_0 + x_1}\cdot\frac{x_0}{x_0})

How did this become the one in subtask 1? I don’t understand :\

The initial variant of the formula presented in subtask 1 was:

E(10010) = (\frac{x_0}{x_0 + x_2 + x_3})\cdot(1) + (\frac{x_2}{x_0 + x_2 + x_3})\cdot(1 + E(10110)) + (\frac{x_3}{x_0 + x_2 + x_3})\cdot(1 + E(11010))

I don’t understand why the two formulas are equal. When I try to use the latter with 000, I can’t receive the former.

2

@aragar

The recurrence is not managed in the same way.

For Subtask 1, we use more detailed states, thanks to bitmaps. As stated in the editorial, E(10010) is the value for the state where we have already clicked on component 1 and component 4. And for instance, E(11110) would be the state where we have clicked on components 1,2,3,4. Please note that with “10010” we have made 2 clicks. And with “11110” we have made 4 clicks.

For Subtask 2 the recurrence is no longer on this kind of states as in sub 1, because there are too many such states. Instead the reccurence is managed with the number of components amongst which you can click.

Now how to link the 2 formulas ?

Imagine you have only 3 components, x0,x1,x2, the component zero (x0) being the “good one” (you click ,you win)

Sub2 formula gives

Expected value = E2(x[0…2]) = 1 + (x1/(x1+x2)) + (x2/(x0+x2))

Now we try with Sub 1 formula

E(000)=1+x1/(x0+x1+x2)(E(010))+x2/(x0+x1+x2)(E(001))=1+1/(x0+x1+x2)(x1E(010)+x2*E(001))

with

E(010)=1+x2/(x0+x2)*E(011)=1+x2/(x0+x2)

and

E(001)=1+x1/(x0+x1)*E(011)=1+x1/(x0+x1)

If you put everything together, you do the same calculation as explained in the editorial for E2(x[0…2])

E(000)=1+1/(x0+x1+x2)(x1(1+x2/(x0+x2)+x2*(1+x1/(x0+x1)))=1+x1/(x0+x1)+x2/(x0+x2)

If you don’t like doing the computation by yourself, you can use Wolfram alpha to check it here

3

I sorry, I guess I didn’t explain my problem properly. I understood the solution and the recurrent formula, and how it was used for forming the formula in sub task 2.

What I didn’t understand is the initial recurrent formula and why it is a formula for the expected value.

The way I understand the formula for the expected value is : \sum NumberOfTries \cdot ProbabilityForThatNumber. Which is the formula I have written in the question. And here again, you are using some other kind of formula. I don’t understand why the two formulas are equal.

4

OK, I see your point.
This is not related to this specific problem.
For inspiration, see Q11 at https://www.codechef.com/wiki/tutorial-expectation

5

Thanks for the article. I went through it even during the contest, but I can’t find anything helpful (for that particular question; awesome article nevertheless) there :\