EllysTwoRatings
SRM 785 · 2020-05-08 · by espr1t
Problem Statement
This problem has a non-standard time limit: 4 seconds.
Elly participates in two programming competitions: TopForces and CodeCoder. Each week she takes part in exactly two matches â on Tuesdays she competes on TopForces and on Saturdays on CodeCoder.
Both TopForces and CodeCoder keep a rating of their users â an integer between 1 and 1000, inclusive. After each match a contestant's rating can change by at most 100 points in either direction â increase, if the contestant performed well, or decrease, if he or she did not.
Elly's performance is very inconsistent. It is so inconsistent that we can assume that after each match her rating becomes any possible new rating with equal probability. Of course, the rating never goes below 1 or over 1000.
Thus, for example, if her current rating is 42, it can become any integer in the range [1, 142] with chance 1/142 for each value. If, instead, her rating is 930 it can go down to 830 or up to 1000 with chance 1/171 for each value in the range. Finally, if it is 666, her new rating will be in [566, 766] with chance 1/201 for each value.
One Sunday Elly thought what a lucky coincidence it would be if both her ratings became equal at some point in time in the next N weeks. We assume ratings are updated immediately after the contest's end, thus TopForces's rating is updated on Tuesday, and CodeCoder's on Saturday. Her current rating in TopForces is A and her current rating in CodeCoder is B. What is the expected chance of this happening?
Notes
- Your return value must have an absolute error at most 1e-9.
Constraints
- N will be an integer between 1 and 52, inclusive.
- A and B will be integers between 1 and 1000, inclusive.
- A and B will be distinct.
13 42 666 Returns: 0.001968164704
It turns out that even after 13 weeks the chance of her ratings becoming equal at any point are very slim.
3 1 1000 Returns: 0.0
The closest ratings she can get after 3 weeks is 301 in TopForces and 700 in CodeCoder. Thus the chance of them ever being equal is zero.
20 216 219 Returns: 0.083322288706
42 973 123 Returns: 0.019345240789
1 333 666 Returns: 0.0
Submissions are judged against all 53 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class EllysTwoRatings with a public method double getChance(int N, int A, int B) · 53 test cases · 2 s / 256 MB per case