Here is the problem statement.
First of all, I'm writing this because I didn't find the editorial for this round anywhere, or else I wouldn't have.
(I am counting on the fact that the expected average of ratings is the same as the expected sum of ratings divided by the number of ratings, so I'll be looking for the expected sum first.Correct me if I'm wrong.)
Here is my approach; there are two cases: (Let n = ceil(N/R)).
N is divisible by R or Elly's rating is in the last N % R ratings.So for each time I take R ratings(n times), I add the sum of them multiplied by 1/R because there's 1/R probability that I'll have any of them in Elly's room, if I don't encounter Elly's rating. Else I just add Elly's rating.Then I just divide this sum by n and return the result.
N isn't divisible by R and the last group of ratings we're going to take(N%R ratings) doesn't contain Elly's rating.There's p = (N % R)/R probability that we'll have n ratings in Elly's room, and q = 1-p probability that we'll only have n-1.So I calculate the expected averages in both cases and return
avg1 * p + avg2 * q.
For avg1: there's 1/(N % R) probability that I'll take any rating in this last group.So I add their sum divided by N % R to the expected sum I already have(of the last N/R groups) and divide it by n. For avg2: I'm not going to add any other rating from this group so I just divide the sum I already have(from the previous groups) by n-1.
My solution fails on 3 of the 5 examples provided with the statement(+- 3 difference), specifically all the examples of the second case. Here is my code.
Can you help correct my reasoning or just propose another solution?