RainForecast
TCO19 SRM 740 · 2018-10-19 · by misof
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
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.
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.
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%.
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.
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!
89
{13, 92, 7}
Returns: 0.7084846399999999
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.
10
{}
Returns: 0.9
Ilko knows that his model is crap and thus he should report the opposite forecast to have a better accuracy.
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.
Submissions are judged against all 81 archived test cases, of which 7 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class RainForecast with a public method double predictRain(int ilkoProb, vector<int> deliverProbs) · 81 test cases · 2 s / 256 MB per case