ExpectedSum
TCO19 SRM 743 · 2018-12-08 · by misof
Problem Statement
This problem has a non-standard time limit: 5 seconds.
Alice came to the blackboard and wrote a sequence of nonnegative integers. You are given this sequence in the
Bob will soon go to the blackboard and edit the sequence in one specific way: For each i, the probability that he will write a minus sign in front of sequence[i] is probMinus[i] percent.
Once Bob finishes his editing, Cecilia will compute the largest sum of a contiguous subsequence of the sequence on the blackboard. (Cecilia's subsequence may be empty, and therefore her result is always nonnegative.)
Return the expected value of the number reported by Cecilia.
Notes
- Minus zero is zero.
- Bob's random choices are mutually independent.
- Your return value must have an absolute or a relative error at most 1e-9.
Constraints
- sequence will contain between 1 and 50 elements, inclusive.
- Each element of sequence will be between 0 and 50, inclusive.
- probMinus will contain the same number of elements as sequence.
- Each element of probMinus will be between 0 and 100, inclusive.
{10, 20, 30}
{0, 0, 0}
Returns: 60.0
Bob will leave the sequence as is, and Cecilia will compute the answer 10 + 20 + 30 = 60.
{10, 40, 20}
{0, 100, 0}
Returns: 20.0
Cecilia will certainly see the sequence {10, -40, 20}. The contiguous subsequence with the largest sum is {20}.
{1, 1, 1}
{50, 50, 50}
Returns: 1.375
If Bob writes three minuses, Cecilia's answer will be 0. If Bob writes two minuses, Cecilia's answer will be 1. If Bob produces {-1,1,1} or {1,1,-1} (probability 2/8), Cecilia's answer will be 2. For {1,-1,1} Cecilia's answer will be 1. Finally, if Bob doesn't write any minuses (probability 1/8), Cecilia will compute the answer 3. Thus, the expected value of Cecilia's answer is (0+1+1+1+2+2+1+3)/8 = 11/8.
{1, 1, 1}
{30, 27, 43}
Returns: 1.89227
Compared to the previous example, Bob is less likely to write the minuses, which increases Cecilia's expected answer slightly.
{47}
{100}
Returns: 0.0
Submissions are judged against all 52 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ExpectedSum with a public method double solve(vector<int> sequence, vector<int> probMinus) · 52 test cases · 2 s / 256 MB per case