Connection Status:
Competition Arena > WaitingForBusAgain

WaitingForBusAgain

TCO19 Round 3A · 2019-04-15 · by lg5293

TCO19 Round 3A · 2019-04-15 · by lg5293 · Dynamic Programming
Class Name: WaitingForBusAgain
Return Type: double
Method Name: expectedBus
Arg Types: (vector<int>)
Problem Statement

Problem Statement

You are waiting at a bus station.

There are n buses. Each of them stops at this station at regular intervals. You know the length of the interval for each bus, but you have no idea when the bus started running, so you do not know the offset.

Formally, you are given a int[] f with n elements. For each valid index i, there is a bus labeled i which comes to your bus stop every f[i] minutes. Additionally, for each bus there is some hidden random real number x[i] such that the exact times when the bus arrives at the bus stop have the form x[i] + k*f[i] for all integers k. We assume that each x[i] was chosen uniformly at random from the half-open interval [0, f[i]), and that all x[i] are mutually independent.

You just arrived at this bus stop. What is the expected value of the label of the next bus that will come to the station?

Notes

  • Your answer will be accepted if your return value has an absolute or a relative error at most 1e-9.

Constraints

  • f will have between 1 and 1,000 elements, inclusive.
  • Each element of f will be between 1 and 1,000,000, inclusive.
Examples
0)
{8,8,8,8}
Returns: 1.5

The setting is symmetric, so all buses have equal probability to be the next bus that arrives. Thus, the answer is (0+1+2+3) / 4 = 1.5

1)
{1,2,3}
Returns: 0.5
2)
{3,2,1}
Returns: 1.5000000000000002

The answer is different from case 1 since the buses have different labels. The bus that has the smallest period now has the biggest label.

3)
{3,1,4,1,5,9,2,6,5,3,5}
Returns: 3.7044469870664325
4)
{26, 19548, 19299, 19431, 39568, 19476, 19726, 19530, 19613,
19529, 19679, 19552, 19706, 19505, 19666, 19349, 19755, 19424,
19486, 19596, 19439, 19500, 19639, 19520, 19472, 19675, 19602,
19552, 19933, 19424, 19316, 19497, 19582, 19531, 19679, 19742,
19896, 19365, 20083, 19542, 19827, 19583, 19592, 19593, 19661,
19340, 19403, 19664, 19690, 19655, 19727, 19661, 19528, 19836,
19819, 19414, 19770, 19500, 19653, 19613, 19579, 19794, 19668,
19729, 19428, 19477, 19733, 19641, 19680, 19594, 19667, 19878,
19571, 19627, 19576, 19422, 19521, 19512, 19481, 19620, 19364,
19487, 19740, 19627, 19795, 19353, 19251, 19865, 19710, 19597,
19610, 19710, 19491, 19598, 19650, 19828, 19726, 19810, 19766,
19692}
Returns: 3.1415926535671885

Submissions are judged against all 90 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class WaitingForBusAgain with a public method double expectedBus(vector<int> f) · 90 test cases · 2 s / 256 MB per case

Submitting as anonymous