TopCoder problem "DriveFailures" used in SRM 359 (Division I Level One , Division II Level Two)



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.
 

Definition

    
Class:DriveFailures
Method:failureChances
Parameters:double[]
Returns:double[]
Method signature:double[] failureChances(double[] failureProb)
(be sure your method is public)
    
 

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 }

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=7702

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10770&pm=7702

Writer:

bmerry

Testers:

PabloGilberto , brett1479 , Olexiy , ivan_metelsky

Problem categories:

Brute Force