Connection Status:
Competition Arena > DriveFailures

DriveFailures

SRM 359 · 2007-07-21 · by bmerry

SRM 359 · 2007-07-21 · by bmerry · Brute Force
Class Name: DriveFailures
Return Type: double[]
Method Name: failureChances
Arg Types: (vector<double>)
Problem Statement

Problem Statement

A redundant storage system can survive a certain number of hard drive failures without losing any data. You are doing some analysis to determine the risk of various numbers of drives failing during one week. Your task is complicated by the fact that the drives in this system have different failure rates. You will be given a double[] containing n elements that describe the probability of each drive failing during a week. Return a double[] containing n + 1 elements, where element i is the probability that exactly i drives will fail during a week. Assume that drive failures are independent events.

Notes

  • The returned value must be accurate to within a relative or absolute value of 1E-9.
  • If events with probabilities p1 and p2 are independent, then the probability of both occurring is p1p2.

Constraints

  • failureProb will contain between 1 and 15 elements, inclusive.
  • Each element of failureProb will be between 0.0 and 1.0, inclusive.
Examples
0)
{1.0, 0.25, 0.0}
Returns: {0.0, 0.75, 0.25, 0.0 }

The first drive is guaranteed to fail, the second has a 25% chance of failing, and the third is guaranteed not to fail. So there is a 25% of two failures and a 75% chance of only one failure.

1)
{0.4, 0.7}
Returns: {0.18000000000000002, 0.54, 0.27999999999999997 }

There is a probability of 0.4 x 0.7 = 0.28 that both drives will fail. The chance that only the first will fail is 0.12 and that only the second will fail is 0.42, for a total probability of 0.54 that exactly one drive will fail. This leaves a probability of 0.18 that no drives will fail.

2)
{0.2, 0.3, 0.0, 1.0, 0.8, 0.9}
Returns: {0.0, 0.011199999999999993, 0.15319999999999995, 0.5031999999999999, 0.2892, 0.0432, 0.0 }
3)
{0.0}
Returns: {1.0, 0.0 }
4)
{0.5}
Returns: {0.5, 0.5 }

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

Coding Area

Language: C++17 · define a public class DriveFailures with a public method vector<double> failureChances(vector<double> failureProb) · 36 test cases · 2 s / 256 MB per case

Submitting as anonymous