GLAYS's blog

Help with TC SRM 577 Div1 250 (About probabilities) [Solved]
By GLAYS, 6 years ago, In English

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?

Thanks.

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

»
6 years ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

Everybody should ask problem-related questions like you — with explanation what you did. *applause*

Avoid float numbers if possible. For example, change ceil((ld)v.size()/20) to (v.size() + 19) / 20. A real value can be calculated with a very small error like 2.999999 instead of 3 and then it will be rounded down to 2. You can google something like "codeforces precision issues" to read more about it.

I'm quite sure that found=(v[i]==elly) should be changed to if(v[i] == elly) found = true. Otherwise you can find her rating but later overwrite it with false.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for replying.

    Changing those two did solve it! Although I'm confused by the boolean expression issue..

    But I'm happy my idea was correct, and I'll be careful next time.

    Thanks a lot :D

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

      The following is equivalent to writing x = t[n-1] (assuming n ≥ 1) — for(int i = 0; i < n; ++i) x = t[i].

      Similarly, your previous code set found to true if and only if the last checked value was equal to elly. For each i, you overwrote a previous value of found.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I can't believe this..

        2 minutes staring at your reply and it's only now that I've got it!

        This was a deadly mistake, and a very very stupid one.. But now that I think about it, I did write that code while I was half sleep at 3 AM.

        One would think that he wouldn't make such mistakes no more.

        Thanks :D

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

          You can also do found |= v[i]==elly;

          → Reply
          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Yes that's what I wanted to do, it was a stupid mistake(I was tired when I wrote it).

            Thanks !

            → Reply