Problem Statement |
| | You have been asked to assist the space medicine community in stocking a space
vehicle with appropriate medical resources to mitigate the likelihood for
medical evacuation of crew members during space flights. The space vehicle has
mass and volume constraints that limit the amount of medical resources
that can be flown. To complete this task, you have agreed to create an
optimization algorithm that identifies the best possible medical kit (medkit) for
meeting constraints on the number of crew member evacuations (P) while
minimizing the medical resource mass and volume.
For your optimization, the space medicine community will provide you with a
list of approved medical resources, with unit mass and volume. Medical
resources in the list will be classified as consumable or non-consumable.
Consumable resources can only be used once, while non-consumables can be used
multiple times.
In order to build the optimization, you will be provided with data from a
previously developed mission simulation. Each trial in the simulation provides
data for a fully treated (all required medical resources are available), and
an untreated scenario (not all required medical resources are available), including the
occurrence of a crewmember evacuation. In the simulation, full treatment of a
condition does not always prevent evacuation, but it does generally lower the
probability of evacuation.
Inputs
The parameters described below will be constant for all tests, and are also
available for download.
The only parameters that will vary between tests are P and C.
- availableResources -- this parameter will give you the different
medical resources that you may include in your medkit. Each element will
be formatted as "RID CONSUMABLE MASS VOLUME".
- RID is an alphanumeric identifier specific to the resource.
- CONSUMABLE is either 0 or 1, where 1 indicates that the resource
will be used up in treatment (like a drug, for instance) and 0
indicates that the resource can be reused (like a thermometer).
- MASS and VOLUME are self-explanatory
- requiredResources -- this parameter will describe the different
medical events that might occur on the missions. Each event can take one
of two courses: a best case course, and a worst case course. These two
courses require different resources for treatment. For simplicity, there
is no middle ground; the event will follow one of these two courses.
Each element of this parameter will be formatted as "MID RID BEST WORST".
- MID is an alphanumeric identifier specific to the medical event. Note
that multiple elements will have the same MID.
- RID is the resource ID (matching the previously described input)
- BEST is the amount of this type of resource required if the event
takes the best course
- WORST is the amount of this type of resource required if the event
takes the worst course
(MID,RID) is a unique key for this input, and thus no two elements will
have the same value for both of these fields.
- missions -- this parameter will
describe a number of missions. Your
goal is to design your medkit tailored to these missions. This input
should be considered the training data, as your medkit will be evaluated
on a different set of missions, which were generated via the same
simulation. Each element
will be formatted as "MISSION ORDER MID WORST TREATED UNTREATED".
- MISSION is an id number for the mission
- ORDER specifies the order within a mission that events occur (each
mission will be sorted by this in the input)
- MID is an alphanumeric identifier specific to the medical event.
- WORST is 1 if the worst case course of this event occurred, and 0
otherwise (best case)
- TREATED specifies the number of evacuations if this event
is treated
- UNTREATED specifies the number of evacuations if this event
is untreated
Output
You should design a medkit and return a String[] where each
element is formatted as "RID QUANTITY", indicating that the resource QUANTITY
of RID should be included (this may be a floating point value).
Your return will be evaluated on each mission independently (resources are
restocked between missions). For a mission,
the events will be evaluated one by one (according to ORDER). If all of the
resources are available to treat the event (under the condition -- best or
worst -- that occurs), those resources will be used to treat it. The number
of evacuations from the event for the treatment status that occurs
will be added to the total number of evacuations. Note that, for simplicity, each medical event is considered independent of the outcome of previous events. This total will be
evaluated over all missions. In pseudocode:
foreach mission
restock resources according to your output
foreach event in mission (in order)
if all resources available to treat event
evacuations += event.treated
decrement consumed resources
else
evacuations += event.untreated
Scoring
For each test case, your input will be evaluated on a set of 10,000 missions, randomly selected
from a corpus of 200,000.
The average number of evacuations per mission must be no more than the input P. Thus the total number of evacuations summed over all missions must be no more than
P*10000.
Given that, your score will be 1000 / (mass + C * volume), where C is an
input parameter. If the evacuations rate exceeds P, your score
will be 0 for that test case. Your overall score will be the sum of your
individual scores.
Offline Tester
A Java implementation of an offline tester is provided to aid in development.
To use it, you must modify your code to read input from standard in and write
output to standard out. Instructions and
download are available at
http://www.topcoder.com/contest/problem/SpaceMedkit/data.html
|
| |
Definition |
| | | Class: | SpaceMedkit | | Method: | getMedkit | | Parameters: | String[], String[], String[], double, double | | Returns: | String[] | | Method signature: | String[] getMedkit(String[] availableResources, String[] requiredResources, String[] missions, double P, double C) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | Events may have no required resources for treatment, in which case they are included only because they are part of the simulation generating the data (and are considered treated). |
| - | The inputs will be given in the same order as the files available for download. |
| - | A tolerance of 1E-12 is given to allow for small rounding errors. Furthermore, solutions which are identical to within this tolerance will be considered ties for scoring purposes. |
| - | There may be ties in the ORDER field for a specific event. This corresponds to multiple crew members being affected simultaneously, and the events will be treated in the order they occur in the input. |
| - | The 10 training cases are based on the training data (a sample of it). |
| - | There are two independent sets of 100,000 missions. One set will be used to generate the provisional tests, the other the final tests. |
| - | Please briefly describe your solution approach in your submission (as you make additional submissions - simply tell us what is different from your previous approach). This will be greatly useful to the contest organizers when they analyze the results after the contest. |
| |
Constraints |
| - | P will be between 0.01 and 0.05, chosen uniformly at random. |
| - | C will be between 0 and 0.001, chosen uniformly at random. |
| - | The time limit is 30 seconds per test case. |
| - | The memory limit is 1024M. |
| |
Examples |
| 0) | |
| | | Returns: "seed = 1<br>
P = 0.033561584816411964<br>
C = 3.9924773370808586E-4<br>
" | |
|
| 1) | |
| | | Returns: "seed = 2<br>
P = 0.027614192161345093<br>
C = 2.561354697676055E-5<br>
" | |
|
| 2) | |
| | | Returns: "seed = 3<br>
P = 0.04267896550286341<br>
C = 1.1968317352293834E-4<br>
" | |
|
| 3) | |
| | | Returns: "seed = 4<br>
P = 0.044863063953766866<br>
C = 1.7385606096367433E-4<br>
" | |
|
| 4) | |
| | | Returns: "seed = 5<br>
P = 0.027333284031164883<br>
C = 4.8598631799855134E-5<br>
" | |
|
| 5) | |
| | | Returns: "seed = 6<br>
P = 0.04934552502325567<br>
C = 6.191817381973387E-4<br>
" | |
|
| 6) | |
| | | Returns: "seed = 7<br>
P = 0.02452927402898118<br>
C = 3.0583416639742443E-4<br>
" | |
|
| 7) | |
| | | Returns: "seed = 8<br>
P = 0.026414984825360775<br>
C = 5.060138074110352E-4<br>
" | |
|
| 8) | |
| | | Returns: "seed = 9<br>
P = 0.03705781766312692<br>
C = 8.319988363621652E-4<br>
" | |
|
| 9) | |
| | | Returns: "seed = 10<br>
P = 0.020911662014465662<br>
C = 2.1404844891576793E-5<br>
" | |
|
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2020, TopCoder, Inc. All rights reserved.