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

Help in a problem.
Автор Matuagkeetarp, история, 5 лет назад, По-английски

Here's a Problem from Atcoder beginner contest 154, I'm unable to understand the problem completely, I mean what they are asking and also the editorial, can someone explain the solution?

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

I think you are not aware about the concept of Expected Value in probability.Read about it here. https://www.statisticshowto.com/probability-and-statistics/expected-value/

Now as each throw is independent so the expected value for any dice is (p+1)/2 where p is the maximum value a dice can show.This is because if a dice with maximum value p is thrown where each outcome is equally likely than expected value is:

1*(1/p)+2*(1/p)+....p*(1/p)=(p*(p+1))/(2*p)=(p+1)/2.

Now the question reduces to finding k consecutive elements in an array of size n(k<=n) which have maximum sum which can be done easily using prefix sums.Time Complexity being o(n).

Have a look at my code here https://ideone.com/QofY1S

→ Ответить
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Thank you for the detailed explanation. I got it completely. I thought we need to start taking element into consideration from k index (forgot it was k consecutive elements in the array). Again thank you.

    → Ответить