Connection Status:
Competition Arena > Disaster

Disaster

TCCC05 Semi 1 · 2005-01-10 · by dgoodman

TCCC05 Semi 1 · 2005-01-10 · by dgoodman · Advanced Math, Dynamic Programming
Class Name: Disaster
Return Type: double
Method Name: expected
Arg Types: (double, vector<string>)
Problem Statement

Problem Statement

We need to get corn to the starving victims of a disaster. We will load up a truck and choose a route to the disaster site. But the roads are bad, and the more we put on the truck, the greater is the probability that we will get stuck somewhere on our route and be unable to deliver the corn.

The probability of successfully completing any segment of our route is the product of the goodness of the road segment (a value between 0.0 and 1.0 inclusive) and the lightness of our load, defined to be 1.0 - b*load where b is a specified constant and load is the amount of corn we carry. Loads that would yield a negative lightness value are not possible.

The road segments go between villages. They are described by a String[] roads. The k-th element of roads lists the goodness of the road segments from village k to each of the villages in order. The goodness from village k to village j may be different from the goodness from village j to village k. (The goodness from village k to village k is always 1.) A goodness of 0 indicates that there is no useable road segment. Village 0 is where the truck and corn are located, while village 1 is the site of the disaster.

Create a class Disaster that contains a method expected. The method is given b (the coefficient in the lightness calculation) and roads. It returns the expected amount of corn that can be delivered if we choose the best load and route.

Constraints

  • b will be between .01 and 1.0 inclusive.
  • roads will contain n elements, where n will be between 2 and 25 inclusive.
  • Each element of roads will contain between 3 and 50 characters inclusive.
  • Each element of roads will contain n values and n-1 spaces separating the values.
  • Each value will be a real value between 0.0 and 1.0 inclusive.
  • Each value will be expressed as "0", "1", or as a decimal point followed by digits ('0'-'9')
  • Each value will contain between 1 and 4 digits inclusive.
  • The k-th value in the k-th element of roads will be "1".
Examples
0)
1.0
{"1 0 1","0 1 0","1 .9 1"}
Returns: 0.13333333333333336

There is only one reasonable route, namely from village 0 to village 2 to village 1. If x is the load we put on the truck, then the probability of getting to village 2 is (1-x)*1.0 and the probability of getting from village 2 to village 1 is (1-x)*.9 so the probability of getting our load to the disaster site is the product of those two. The expected amount of corn delivered is x times that probability giving x*(1.0*(1-x))*(.9*(1-x)). This is maximized when we make the load be 1/3 and gives us an expected amount of (1/3)*(2/3)*(.6)

1)
0.5
{"1 0 1 0","0 1 0 0","0 0 1 0","1 .9 1 1"}
Returns: 0.0

There is no route between village 0 and village 1.

2)
.8
{"1 .8 .6","1 1 1","1 1 1"}
Returns: 0.25
3)
.01
{"1 .6 1","0 1 0","1 1 1"}
Returns: 15.0
4)
.01
{"1 .58 1","0 1 0","1 1 1"}
Returns: 14.814814814814813
5)
.8
{"1 .0300 .98 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0",
"1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
"1 .0517 1 .98 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0",
"1 .0740 1 1 .98 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0",
"1 .0973 1 1 1 .98 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0",
"1 .1214 1 1 1 1 .98 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0",
"1 .1465 1 1 1 1 1 .98 0 0 0 0 0 0 0 0 0 0 0 0 0 0",
"1 .1725 1 1 1 1 1 1 .98 0 0 0 0 0 0 0 0 0 0 0 0 0",
"1 .1995 1 1 1 1 1 1 1 .98 0 0 0 0 0 0 0 0 0 0 0 0",
"1 .2275 1 1 1 1 1 1 1 1 .98 0 0 0 0 0 0 0 0 0 0 0",
"1 .2567 1 1 1 1 1 1 1 1 1 .98 0 0 0 0 0 0 0 0 0 0",
"1 .2869 1 1 1 1 1 1 1 1 1 1 .98 0 0 0 0 0 0 0 0 0",
"1 .3182 1 1 1 1 1 1 1 1 1 1 1 .98 0 0 0 0 0 0 0 0",
"1 .3507 1 1 1 1 1 1 1 1 1 1 1 1 .98 0 0 0 0 0 0 0",
"1 .3843 1 1 1 1 1 1 1 1 1 1 1 1 1 .98 0 0 0 0 0 0",
"1 .4192 1 1 1 1 1 1 1 1 1 1 1 1 1 1 .98 0 0 0 0 0",
"1 .4554 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 .98 0 0 0 0",
"1 .4929 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 .98 0 0 0",
"1 .5317 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 .98 0 0",
"1 .5718 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 .98 0",
"1 .6134 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 .98",
"1 .6565 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1"}
Returns: 0.009382592592592593

{"1 .0300 .98 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0", "1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1", "1 .0517 1 .98 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0", "1 .0740 1 1 .98 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0", "1 .0973 1 1 1 .98 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0", "1 .1214 1 1 1 1 .98 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0", "1 .1465 1 1 1 1 1 .98 0 0 0 0 0 0 0 0 0 0 0 0 0 0", "1 .1725 1 1 1 1 1 1 .98 0 0 0 0 0 0 0 0 0 0 0 0 0", "1 .1995 1 1 1 1 1 1 1 .98 0 0 0 0 0 0 0 0 0 0 0 0", "1 .2275 1 1 1 1 1 1 1 1 .98 0 0 0 0 0 0 0 0 0 0 0", "1 .2567 1 1 1 1 1 1 1 1 1 .98 0 0 0 0 0 0 0 0 0 0", "1 .2869 1 1 1 1 1 1 1 1 1 1 .98 0 0 0 0 0 0 0 0 0", "1 .3182 1 1 1 1 1 1 1 1 1 1 1 .98 0 0 0 0 0 0 0 0", "1 .3507 1 1 1 1 1 1 1 1 1 1 1 1 .98 0 0 0 0 0 0 0", "1 .3843 1 1 1 1 1 1 1 1 1 1 1 1 1 .98 0 0 0 0 0 0", "1 .4192 1 1 1 1 1 1 1 1 1 1 1 1 1 1 .98 0 0 0 0 0", "1 .4554 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 .98 0 0 0 0", "1 .4929 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 .98 0 0 0", "1 .5317 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 .98 0 0", "1 .5718 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 .98 0", "1 .6134 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 .98", "1 .6565 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1"}

Submissions are judged against all 109 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Disaster with a public method double expected(double b, vector<string> roads) · 109 test cases · 2 s / 256 MB per case

Submitting as anonymous