Get Time
long_comps_topcoder  Problem Statement
Contest: NASA-TopCoder - 0132
Problem: SpaceMedkit

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.
  1. 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
  2. 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.
  3. 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)
    
seed = 1
P = 0.033561584816411964
C = 3.9924773370808586E-4
1)
    
seed = 2
P = 0.027614192161345093
C = 2.561354697676055E-5
2)
    
seed = 3
P = 0.04267896550286341
C = 1.1968317352293834E-4
3)
    
seed = 4
P = 0.044863063953766866
C = 1.7385606096367433E-4
4)
    
seed = 5
P = 0.027333284031164883
C = 4.8598631799855134E-5
5)
    
seed = 6
P = 0.04934552502325567
C = 6.191817381973387E-4
6)
    
seed = 7
P = 0.02452927402898118
C = 3.0583416639742443E-4
7)
    
seed = 8
P = 0.026414984825360775
C = 5.060138074110352E-4
8)
    
seed = 9
P = 0.03705781766312692
C = 8.319988363621652E-4
9)
    
seed = 10
P = 0.020911662014465662
C = 2.1404844891576793E-5

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)2010, TopCoder, Inc. All rights reserved.