dhruvmullick's blog

Need help with #259Div1 A problem (a problem on Expectation values)
By dhruvmullick, 9 years ago, In English

I saw a solution for Little Pony and Expected Maximum but couldn't really understand why it works. Can someone explain the logic behind it?
I have seen the tutorial, but it doesn't explain this approach. 

double p = m;
for(int i = 1; i < m; i++)
    p -= pow((double) i / m, n);
printf("%.16f\n", p);
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

You have troubles in simplifying sum from tutorial to this one? I written solution but can't insert image for some reason =/ So, here.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oh. Thank you. I had thought that this was a different, perhaps cleverer, approach. Didn't think it was just a reduced form.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Well, but problem remains the same, right? :) Almost in any math problem you can prove some equivalence between different approaches. Maybe, there is also some naive explanation of this answer... But I don't know. At that contest I had terrible formula (7314095), but it can be reduced to this one too.

      → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The derivation of the formula in tutorial is quite simple —
Let us assume that we have Xj which denotes the number of throws when the maximum number appearing on dice is j, So Xj is given by —
Xj = jn — (j-1)n
(Assume that we have n places to fill such that their maximum is j, So the arrangement should contain at least one j, so consider each permutation formed by numbers from 1 to j and subtract each permutation formed by numbers from 1 to (j-1). The resulting value will contain each permutation such that it contains at least one j)
Now finding out the expected value is quite easy
Hope it helps :)

→ Reply