Statistics

Problem Statement for "RainForecast"

Problem Statement

Ilko is a meteorologist whose goal is to predict the weather for the report given in the evening news on TV. Ilko has a complex numerical model that tries to predict a single boolean: whether it will rain tomorrow. The success rate of the model's predictions is ilkoProb percent. Every day at 4:47 pm, Ilko runs the model, reads its output, thinks about it, and finally he sends a one-word instruction to the TV station: he either tells them to broadcast the word "sunny" or the word "rainy".

However, the TV station does not simply broadcast the word Ilko sent. There is a whole chain of people who get involved: Ilko reports the forecast to his contact person, that person tells their secretary to pass it on, the secretary writes it down and uses internal mail to send it to a different floor, and so on. The problem is that each person in the chain will, with some probability, mix up the message and deliver the opposite forecast from the one they received.

You are given the int[] deliverProbs. Each element of deliverProbs corresponds to one person in the chain, in the order in which the message passes through them. Person i will correctly deliver the forecast they receive with probability deliverProbs[i] percent.

Ilko knows all the information mentioned above, including all the probabilities. His reputation depends on the accuracy of the forecast that actually gets aired by the TV station. Thus, he will do all he can to maximize the accuracy of that forecast.

Compute and return the probability that the forecast aired by the TV station tonight will match the weather tomorrow.

Definition

Class:
RainForecast
Method:
predictRain
Parameters:
int, int[]
Returns:
double
Method signature:
double predictRain(int ilkoProb, int[] deliverProbs)
(be sure your method is public)

Notes

  • Formally, assume that all random events mentioned in the statement are mutually independent. In particular, the probability that Ilko's model correctly predicts whether it will rain tomorrow is ilkoProb/100.
  • Your answer will be accepted if it has a relative or an absolute error up to 1e-9.
  • Remember that Ilko has perfect knowledge of all things mentioned in the problem statement, and that he is actively trying to maximize the probability that the weather will match the forecast broadcast by the station.

Constraints

  • ilkoProb will be between 0 and 100, inclusive.
  • deliverProbs will have between 0 and 50 elements, inclusive.
  • Each element of deliverProbs will be between 0 and 100, inclusive.

Examples

  1. 93

    {}

    Returns: 0.93

    Ilko's model correctly predicts rain with probability 93%. There are no people involved in the TV station. Thus, what happens is that: Ilko looks at the prediction given by his model. Ilko sends that prediction to the TV station. The prediction goes straight into the broadcast. Obviously, the forecast aired on the news will match reality with probability 93%.

  2. 93

    {50}

    Returns: 0.5

    Ilko uses the same model, but now he reports to a person who always loses it and then just flips a coin to determine what forecast the station will broadcast that night.

  3. 100

    {90,90}

    Returns: 0.82

    In this test case, Ilko's model is completely accurate. Sadly, the forecast goes through two people before it gets aired, and each of them will make a mistake with probability 10%. That's still good enough to mostly preserve the forecast Ilko reports to the station, but they do introduce some mistakes here and there. Note that the actual probability that the station airs the correct forecast is 82%, not 81%. This is because the following is also a possible chain of events: Ilko reports the correct forecast to the station. The first person makes a mistake and reports the opposite forecast to the second person. The second person also makes a mistake and broadcasts the opposite forecast from the one they received - but that is the forecast Ilko originally sent!

  4. 89

    {13, 92, 7}

    Returns: 0.7084846399999999

  5. 50

    {3, 17, 92, 34, 2, 14}

    Returns: 0.5

    This time, the accuracy of Ilko's model is as good as a coin flip. The people at the TV station don't really matter, the final forecast will still be correct with probability exactly 50 percent.

  6. 10

    {}

    Returns: 0.9

    Ilko knows that his model is crap and thus he should report the opposite forecast to have a better accuracy.

  7. 90

    {0}

    Returns: 0.9

    Ilko knows that his model is good, but he also knows that the person in the TV station will broadcast the opposite from what he tells them. Thus, he should intentionally report the opposite.

  8. 45

    {83,82,92,12}

    Returns: 0.513483008

  9. 53

    {0,99,100,1,100,1,100,99,0,0,1,99,1,100,100,100,99,100,1,99,99,0,100,99,100,0,0,99,99,100,99,0,100,1,100,0,0,99,100,1,100,100}

    Returns: 0.520854059925711

  10. 2

    {0,98,100,98,2,2,0,98,2,2,2,1,0,1,98,0}

    Returns: 0.8192526318031187

  11. 70

    {17,64,21,93,74,81,38,4,71,99,36,82,32,48,78,90,1,58,71,40,35,57,98,66,24,46,67,66,63,26,46,94,75,66,6,61,23}

    Returns: 0.5

  12. 44

    {97,2,2,97,97,2,99,0,97,97,2,2,99,98,3,98,100,3,3,1,100,3,99,99,0,100,100,97,2,3,100,3,99,97,100,98,99}

    Returns: 0.5161375267206443

  13. 50

    {93,99,7,5}

    Returns: 0.5

  14. 50

    {4,4,96,95,4,4,2,3,97,100,4,95,100,0,4,1,0,4,5,0,99,2,97,4,95,100,0,1,2,98,96,96,95,97,95,0,2,96,100}

    Returns: 0.5

  15. 98

    {99,6,5,94,7,3,100,5,98,1,4,100,5,97,5,97,100,96,99,94,93,100,97,6,100,97,5,95,7,99,4,2,97,7,4,1,4}

    Returns: 0.5316956666355555

  16. 68

    {29,90,29,79,90,28,3,9,19,26,1,88,6,70,70,84,1,91,99,86,77,23,92}

    Returns: 0.5000117821054181

  17. 47

    {76,89,1,36,8,5}

    Returns: 0.5025242077952

  18. 54

    {78,18,96,83,8,2,18,26,2,4,16,81,82,83,19,5,7,96,81,75,86,87,19,100,75,85,90}

    Returns: 0.5000042934970234

  19. 71

    {88,99,96,12,3,89,18,100,11,19,87,10,92,90,3,5,9,86,96}

    Returns: 0.5045367476587197

  20. 14

    {9,92,10,10,100,6,7,97,11}

    Returns: 0.5880601037668353

  21. 60

    {34,16,8,83,93,65,93,23,82,20,87,72,7,89,79,94,13,17,88,31}

    Returns: 0.5000087274267827

  22. 48

    {0,99,100,0,0,100,99,1,100,1,0,99,0,99,99,0,99,100,99,1,1,0,0,100,1,99,100,1,100,0,99,99,100,99,1,1,99,99,1,0,1}

    Returns: 0.5125669456430424

  23. 39

    {89,100}

    Returns: 0.5858000000000001

  24. 1

    {92,16,86,1,96,14,7,88,17,17,83,83,18,5,92,94,84,86,10,93,7,4,14,10,10,8,92,4,2,1,17,9,10,98,8,9,82,4,7,91}

    Returns: 0.50006158854695

  25. 86

    {25,9,23,13,92,94,100,20,12,25,5,94,81,80,77,20,9,99,71,93,74,5,83,75,91,19,74,29,21,81,82,96,12,84,78,17,92,90,28,88,4,77,7,100,17,75,88}

    Returns: 0.5000000039191174

  26. 91

    {2,7,89,98,92,11,99,15,97,95,8,84}

    Returns: 0.5550523602325791

  27. 97

    {5,96,99,4,6,3,99,8,93,0}

    Returns: 0.7054737923018891

  28. 87

    {3,97,94,89,100,95,1,95,8,9,97,8,12,11,100,97,13,97,5,87,98,9,100,7,6,6,7,6,11,97,8,87,93,96,9}

    Returns: 0.5029341311851842

  29. 86

    {97,91,93}

    Returns: 0.7386396799999999

  30. 69

    {94,100,8,95,4,0,100,4,95,3,3,98,0,98,4,8,97,93,99,4,92,92,93,98,2}

    Returns: 0.5246991050202049

  31. 2

    {97,1,2,1,97,3}

    Returns: 0.8675768761548801

  32. 89

    {44,68,32,76,8,10,21,37,65,90,67,59,65,43,90,25,35,3,87,12,34,99,84,17,42,78,100,64,28,93,77}

    Returns: 0.5000000000090247

  33. 6

    {98,41,44,23,14,87,32,18,31,2,68,91,23,79,8,73,64,43,62,1,27,43,6,6,13,89,6,65,1,89,42}

    Returns: 0.5000000000675451

  34. 89

    {7,99,95,17,2,84,16,11}

    Returns: 0.5676019525839258

  35. 45

    {100,0,100,96,89,100,89,10,8,3,92,97,94,0,95,1,91}

    Returns: 0.5088841608517034

  36. 26

    {3,81,88,94,92,93,95,12,99,1,2,8,85,4,100,9}

    Returns: 0.5189044165626231

  37. 33

    {11,98,98,83,79,81,95,97,87,7,1,99,80,15,6,78,18,16,90,96,3,7,22}

    Returns: 0.5004500940963704

  38. 77

    {90,100,23,16,80,82,79}

    Returns: 0.517665081344

  39. 73

    {10,9,79,88,21,96,16,14,83,12,2,83,16,21,95,2,89,94,22,80,6,100,17,12,96,11,3,94,92,77,87,1,4,89,4,20,4}

    Returns: 0.5000136315022895

  40. 22

    {0,0,100}

    Returns: 0.78

  41. 95

    {13,86,5,84,0,95,96,11,100,94,95,84,81,95,97,17}

    Returns: 0.5176682352801152

  42. 92

    {71,11,17,94,97,36,28,94,21,23,22,13,89}

    Returns: 0.5008244743093707

  43. 30

    {0,97,98,97,3,100,97,98,1,97,100,2,3,1,97,99,100,1,2,100,100,98,3,1}

    Returns: 0.589854404050413

  44. 26

    {92,0,84,87}

    Returns: 0.6014451199999999

  45. 99

    {96,17,17,91,99,89,14,92,85,83,5,88,14,91,97,11,2,1,92,13,94,94}

    Returns: 0.5046116743564251

  46. 12

    {88,12,99,0,13,5,7,12,7,2,2,13,3,9,94,6,12,3,90,99,92,88,87,97,97,9,90,4,11,4,0,3,90,13}

    Returns: 0.5018469889101547

  47. 70

    {}

    Returns: 0.7

  48. 19

    {71,5,39,58,82,81,31,81,81,38,80,79,12,39,99}

    Returns: 0.5000032718066494

  49. 65

    {65,73,40,41,94,87,69,62,20,12,11,87,77,90,58,63,7,26,1,24,58,7,15,13,73,12,37,70,4}

    Returns: 0.5000000001049929

  50. 100

    {95,95,2,1,98,2,1,99,98,5,95,96,0,5,99,96,96,97,95}

    Returns: 0.652372162619157

  51. 64

    {17,27,93,24,86,2,4,77,73,97,27,2,3,2}

    Returns: 0.5011246846066173

  52. 69

    {15,34,81,0,68,30,13}

    Returns: 0.502811820032

  53. 42

    {95,7,71,1,69,13,63,80,23,82,51,36,82,79,67,73,28,9,61,14,19,52,20,20,25,51,34,8,97,92,67,94,27,54,93,60,29,83,98,15,82,99,64,56}

    Returns: 0.5

  54. 82

    {11,37,76,5,64,32,85,66,75,73,25,11,69,66,74,76,90,3,76,20,83,24,24,23,93,7}

    Returns: 0.5000000312217076

  55. 91

    {75,77,23,79,10,26,84,22,64,15,19,73,65,22,60,87,70,85,83,24,23,0,17,93,79,85}

    Returns: 0.5000000842639122

  56. 72

    {}

    Returns: 0.72

  57. 56

    {95,90,11,90,13,94,17,19,12,92,3,1,9,85,16,93,90,16,93,9,96,2,84,85}

    Returns: 0.5002286976141012

  58. 86

    {8,88,9,100,10,95,13,4,14,94,87,97,91}

    Returns: 0.5333848838259831

  59. 63

    {0,1,100}

    Returns: 0.6274000000000001

  60. 96

    {93,93,94,7,91,8,4,100,0,10,2,91,97,93,93,99,93,99,100,91,92,1,7,3,91,98,7,93,4,93,3,8,4,7,93,8,90,95,10,1,6}

    Returns: 0.5033249370456566

  61. 90

    {0,84,3,19,86,84,11,3,4,2,8,4,97,90,87}

    Returns: 0.5216136466268269

  62. 51

    {88,8,13,15,95,0,0,1,10,89,10,97}

    Returns: 0.5013686539447992

  63. 44

    {98,0,100,96,4,96,95,98,100,100}

    Returns: 0.5387524984832001

  64. 52

    {98,87,85,96,3,95,91,2,100}

    Returns: 0.5060936045133824

  65. 67

    {17,95,82,95,17,7,14,17,83,2,2,16,85,17,81,78,100,87,4,19,91,17,99,19,3,18,9,86,82,94}

    Returns: 0.5000288999630276

  66. 42

    {95,1,5,98,14,85,13,91,87,98,11,11,11,1,0,91,3,94,7,88,89,92,92,8,9,99,96,99,2,98,7,7,98,95,95,13,88,9,2,6,85,89,13,8,10,1,87}

    Returns: 0.5000371915342323

  67. 63

    {75,92,19,9,93,78,86,86,10,10,75,99,2,77,83,85,88,11,80,88,97,96,96,99,85,5}

    Returns: 0.5000691155628673

  68. 51

    {51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51}

    Returns: 0.5

  69. 0

    { }

    Returns: 1.0

  70. 90

    {0 }

    Returns: 0.9

  71. 100

    {0 }

    Returns: 1.0

  72. 10

    { }

    Returns: 0.9

  73. 20

    { }

    Returns: 0.8

  74. 90

    {10 }

    Returns: 0.8200000000000001

  75. 80

    {0 }

    Returns: 0.8

  76. 10

    {100 }

    Returns: 0.9

  77. 93

    {1 }

    Returns: 0.9214000000000001

  78. 1

    { }

    Returns: 0.99

  79. 100

    {1 }

    Returns: 0.99

  80. 7

    { }

    Returns: 0.9299999999999999

  81. 12

    {3, 86, 9, 94, 2, 3, 1, 0, 100, 0, 100 }

    Returns: 0.6641215589285888

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: