Блог пользователя dhruvmullick

Need help with #259Div1 A problem (a problem on Expectation values)
Автор dhruvmullick, 9 лет назад, По-английски

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 лет назад, # |
  Проголосовать: нравится +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 лет назад, # ^ |
      Проголосовать: нравится 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 лет назад, # ^ |
        Проголосовать: нравится 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 лет назад, # |
  Проголосовать: нравится 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 :)

→ Ответить