PackageShipping

TCCC05 Round 3 · 2005-01-10 · by lars2520

TCCC05 Round 3 · 2005-01-10 · by lars2520 · Dynamic Programming, Graph Theory

Show categories

Class Name: PackageShipping

Return Type: double

Method Name: ship

Arg Types: (vector<string>, string, string, int, int)

Problem Statement

Shipping is a complicated business, particularly when you are shipping fragile items. To do well, you need to deliver packages quickly, at a low cost, and without breaking them. To this end, you would like software to help you send a package, given the package's cost and the maximum delivery time. There are a number of different routes that are continually traversed by your fleet of trucks. Each route takes a certain amount of time, and it costs a certain amount to send a package along that route. Furthermore, there is a probability associated with each route indicating the percent chance that a package will be damaged along that route.

As the shipping company, you must pay the cost of an item if it is damaged during shipping. Your goal is to find the way to ship an item with the lowest expected cost. For example, if one shipping plan has a cost of X, but a 50% probability of damaging an item, it might end up with a higher expected cost than a plan that has a cost of 2X but only a 5% chance of damaging an item.

You will be given a String[], routes, each element of which represents a single route and will be formatted as
"ORIGIN DESTINATION TIME COST PROBABILITY"
where ORIGIN and DESTINATION are city codes (sequences of uppercase letters), TIME is an integer between 1 and 50, COST is an integer between 1 and 20, and PROBABILITY is a real number between 0 and 10, all ranges inclusive. The inputs origin and destination are the starting and ending points for the package to be delivered. time is the maximum allowed delivery time, and is in the same units as TIME in routes. cost is the cost of the package, and is in the same units as COST in routes. You should find the shipping plan with the lowest expected cost, and return that cost as a double.

Notes

A route from A to B does not imply a route from B to A.
You may assume that there is no waiting time when a package is transferred from one route to another.
You won't know that a package is damaged until it reaches its destination, so you must still send it all the way to the destination, even if it is damaged at the beginning of the trip.

Constraints

routes will contain between 1 and 50 elements, inclusive.
Each element of routes will be formatted as "ORIGIN DESTINATION TIME COST PROBABILITY", with no double, leading or trailing spaces.
Each element of routes will contain between 9 and 50 characters, inclusive.
ORIGIN and DESTINATION will each be sequences of uppercase letters ('A'-'Z')
In no element of routes will ORIGIN equal DESTINATION.
TIME will be an integer between 1 and 50, inclusive, with no leading zeros.
COST will be an integer between 1 and 20, inclusive, with no leading zeros.
PROBABILITY will be between 0 and 10, inclusive, and will be formatted as a sequence of 1 or more digits ('0'-'9') and an optional decimal point (extra leading/trailing zeros allowed).
origin will be a sequence of uppercase letters matching an ORIGIN in some element of routes.
destination will be a sequence of uppercase letters matching a DESTINATION in some element of routes.
time will be between 1 and 100, inclusive.
packageCost will be between 1 and 1,000,000,000, inclusive.
There will be some way to deliver the package in the given amount of time or less.
No two elements of routes will have the same origin and destination.
origin and destination will not be the same.

Examples

{"SANFRAN CHICAGO 20 3 0.4",
 "SANFRAN MEMPHIS 30 5 1.0",
 "CHICAGO NEWYORK 15 2 2.0",
 "MEMPHIS NEWYORK 8 6 0.1"}
"SANFRAN"
"NEWYORK"
100
100
Returns: 7.392000000000005

There are two possibilities here. We can ship the package through either CHICAGO or MEMPHIS. If we ship the package through CHICAGO, it will cost us 5, and there will be a 2.392% chance that it will be damaged. If we ship through MEMPHIS, it will cost 11, but there will only be a 1.099% chance of damage. Since the package has a cost of 100, the first option will have an expected cost of 7.392, while the second will have an expected cost of 12.099.

{"SANFRAN CHICAGO 20 3 0.4",
 "SANFRAN MEMPHIS 30 5 1.0",
 "CHICAGO NEWYORK 15 2 2.0",
 "MEMPHIS NEWYORK 8 6 0.1"}
"SANFRAN"
"NEWYORK"
100
10000
Returns: 120.90000000000055

Here we have the same shipping routes as example 0, but for a more expensive package. Shipping through CHICAGO will have an expected cost of 5 + 239.2 = 244.2, while MEMPHIS will have an expected cost of 11 + 109.9 = 120.9.

{"SANFRAN CHICAGO 20 3 0.4",
 "SANFRAN MEMPHIS 30 5 1.0",
 "CHICAGO NEWYORK 15 2 2.0",
 "MEMPHIS NEWYORK 8 6 0.1"}
"SANFRAN"
"NEWYORK"
36
10000
Returns: 244.20000000000053

In this case, the time constraint forces us to send the package along the more expensive route through CHICAGO.

{"SANFRAN CHICAGO 20 3 0.4",
 "SANFRAN MEMPHIS 30 5 1.0",
 "CHICAGO NEWYORK 15 2 2.0",
 "MEMPHIS NEWYORK 8 6 0.1"}
"SANFRAN"
"NEWYORK"
100
464
Returns: 16.098880000000023

Replace with large example.

{"SANFRAN CHICAGO 20 3 0.4",
 "SANFRAN MEMPHIS 30 5 1.0",
 "CHICAGO NEWYORK 15 2 2.0",
 "MEMPHIS NEWYORK 8 6 0.1"}
"SANFRAN"
"MEMPHIS"
100
1
Returns: 5.01

{"A B 1 1 1",
"B C 1 1 1",
"C D 1 1 1",
"D E 1 1 1",
"E F 1 1 1",
"F G 1 1 1",
"G H 1 1 1",
"H I 1 1 1",
"I J 1 1 1",
"J K 1 1 1",
"K L 1 1 1",
"L M 1 1 1",
"M N 1 1 1",
"N O 1 1 1",
"O P 1 1 1",
"P Q 1 1 1",
"Q R 1 1 1",
"R S 1 1 1",
"S T 1 1 1",
"T U 1 1 1",
"U V 1 1 1",
"V W 1 1 1",
"W X 1 1 1",
"X Y 1 1 1",
"Y Z 1 1 1",
"A C 1 1 1",
"B D 1 1 1",
"C E 1 1 1",
"D F 1 1 1",
"E G 1 1 1",
"F H 1 1 1",
"G I 1 1 1",
"H J 1 1 1",
"I K 1 1 1",
"J L 1 1 1",
"K M 1 1 1",
"L N 1 1 1",
"M O 1 1 1",
"N P 1 1 1",
"O Q 1 1 1",
"P R 1 1 1",
"Q S 1 1 1",
"R T 1 1 1",
"S U 1 1 1",
"T V 1 1 1",
"U W 1 1 1",
"V X 1 1 1",
"W Y 1 1 1",
"X Z 1 1 1",
"Y A 1 1 1"}
"A"
"Z"
100
100
Returns: 25.247897700103216

This one has lots of routes.

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

Coding Area

Language: C++17 · define a public class PackageShipping with a public method double ship(vector<string> routes, string origin, string destination, int time, int packageCost) · 41 test cases · 2 s / 256 MB per case