SRM 740, D1, 250-Pointer (RainForecast)

James S. Plank

Sat Oct 27 12:44:22 EDT 2018

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
Problem Given in Topcoder: October, 2018
Competitors who opened the problem: 157
Competitors who submitted a solution: 150
Number of correct solutions: 75
Accuracy (percentage correct vs those who opened): 47.8
Average Correct Time: 13 minutes, 59 seconds.

This problem is less about programming, and more about calculating probabilities. First, convert all of those integer percentages into doubles that are actual probabilities.

Next, calculate the probability that Ilko's model gets it correct. Call that C₀. After calculating that, calculate the probability that Ilko's model gets it incorrect. Call that I₀.

Now, consider each person in the delivery chain. Call that person i (zero indexed). For each of these people, you can calculate:

C_i+1, which is the probability that person i delivers the correct forecast. This will be a function of the person's probability, C_i and I_i.
I_i+1, which is the probability that person i delivers the incorrect forecast. You can calculate that from C_i+1.

At the end of this process, you can simply return the greater of C_n and I_n, where n is the size of deliverProbs.

Working through the examples

Here are the C_i and C_i for all of the examples, followed by the return values:

UNIX> a.out 0
 i    C_i    I_i
-- ------ ------
 0 0.9300 0.0700
0.93
UNIX> a.out 1
 i    C_i    I_i
-- ------ ------
 0 0.9300 0.0700
 1 0.5000 0.5000
0.5
UNIX> a.out 2
 i    C_i    I_i
-- ------ ------
 0 1.0000 0.0000
 1 0.9000 0.1000
 2 0.8200 0.1800
0.82
UNIX> a.out 3
 i    C_i    I_i
-- ------ ------
 0 0.8900 0.1100
 1 0.2114 0.7886
 2 0.2576 0.7424
 3 0.7085 0.2915
0.708485
UNIX> a.out 4
 i    C_i    I_i
-- ------ ------
 0 0.5000 0.5000
 1 0.5000 0.5000
 2 0.5000 0.5000
 3 0.5000 0.5000
 4 0.5000 0.5000
 5 0.5000 0.5000
 6 0.5000 0.5000
0.5
UNIX>