### dhruvmullick's blog

By dhruvmullick, 9 years ago,

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);

• 0

 » 9 years ago, # |   +1 You have troubles in simplifying sum from tutorial to this one? I written solution but can't insert image for some reason =/ So, here.
•  » » 9 years ago, # ^ |   0 Oh. Thank you. I had thought that this was a different, perhaps cleverer, approach. Didn't think it was just a reduced form.
•  » » » 9 years ago, # ^ |   0 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.
 » 9 years ago, # |   0 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 :)