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

Автор Matuagkeetarp, история, 7 лет назад, По-английски

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
  • Проголосовать: не нравится

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