Matuagkeetarp's blog

Help in a problem.
By Matuagkeetarp, history, 4 years ago, In English

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?

  • Vote: I like it
  • +3
  • Vote: I do not like it

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

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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    → Reply