

Problem Statement 
Contest:
2008 TopCoder Open Marathon Online Round 2
Problem: Epidemic
Problem Statement   You will be given a graph describing friendship between people. In the graph, each node represents a person, and each edge represents a friendship relationship. Your task is to come up with a scheme to prevent the spread of an epidemic disease by inoculating certain people, and reducing contact between some pairs of people.
The spread of the disease will be modelled by a simple simulation. If a person u with a friend v becomes infected on day D, then on day D+1 v becomes infected with probability p_{v}. To combat the spread of the disease, you may both inoculate people, and decrease the probability along an edge (by reducing contact between people). If you chose to inoculate a person, you reduce that persons probability of being infected from p_{v} to p_{v}*X, for some constant X. Reducing the probability along an edge also reduces the infection probability to p_{v}*Y, for some constant Y. These two effects are cumulative, so the infection probability can be p_{v}*X*Y if you inoculate a person and reduce an edge.
Prior to the start of the epidemic, you may inoculate as many people as you like, but you may not reduce the probability along any edges. Once the epidemic starts, you may inoculate people and reduce edge probabilities as much as you want each day. If you inoculate a person on day D, then that person's chance of being infected is reduced on day D+1. The epidemic will start on day 1 with a seed population becoming infected.
Unfortunately, the disease may not be easy to diagnose, and if a person becomes infected on day D, you will not learn about it until day D+K, for some small constant K. Thus, a sample epidemic might go like this, with K = 2:
 Prior to day 1, inoculate a few people
 Day 1  A and B become infected
 Day 2  The disease spreads to A's friend C
 Day 3  The disease spreads from C to D. You learn that A and B are infected, you inoculate C, D and reduce the probability along the edge from D to E.
 Day 4  The disease would have spread from D to E, but you reduced that edge's probability just in time. You learn that C is infected, but do nothing.
 Day 5  The epidemic is over, since no one new was infected on day 4. You learn that D is infected and inoculate F and G.
 Day 6  You see no new infections, and know that the epidemic is over.
Your task is to reduce the overall cost of the epidemic. Each person that is infected has a cost of infection, while each inoculation costs inoculation, and each edge reduction costs edgeReduce.
At the start of the simulation, you will be given a description of the friendship graph as a int[], g. Each pair of elements in g represents an edge. So for all i, g[2*i] and g[2*i+1] are joined by an (undirected) edge. Each person will also be categorized as low, medium, or high risk for infection. This will be done as follows, where rand() produces a random number in [0,1):
p = (p_{u}p_{low})/(p_{high}p_{low})
if(p < 0.5 && rand() < 12*p) risk = low
else if(p > 0.5 && rand() < 2*p1) risk = high
else risk = medium
This will be given to you as a int[], where 1 is low risk and 3 is high risk. After this (and some other) initial data is given, you should return a int[] representing the people to inoculate before the start of the epidemic. The simulation will then proceed, with your function being called every day, telling which people were infected K days ago. The first time it is called will be on day K+1. On each day, you should return a String[], where each element is either "<idx>" to inoculate person <idx> or "<u> <v>" to reduce the probability along an edge between <u> and <v>.
X and Y will be randomly chosen between 0.05 and 0.5. infection will be randomly chosen between 500 and 5000. inoculation will be randomly chosen between 100 and 1000. edgeReduce will be randomly chosen between 50 and 150. Two parameters p_{low} and p_{high} will be chosen by picking two random numbers between 0.1 and 1, and ordering them. Each p_{v} will then be chosen randomly between p_{low} and p_{high}. K will be 0, 1 or 2. A seed population will be selected by choosing a random person, and all of his friends. This group of people will all become infected on day 1.
The graph will be generated by sampling from a much larger graph from an online social networking site. This will be done by first selecting M, the number of vertices to sample, between 100 and 100,000. A single seed vertex will by selected at random from the entire graph. To add each subsequent vertex, a random vertex will be chosen from those already in the sample and one of that vertex's friends will then be chosen at random. If that node has already been added, a new random vertex and a new random friend will be chosen until an unadded vertex is found. The edge set will consist of all edges in the original graph, both of whose endpoints are in the node set after all M nodes have been selected.
Your score for an individual test case will simply be the total cost incurred. Your overall score will be computed using relative scoring. For each test case we find the best (lowest) cost: BEST. We then take your score, YOU, and compute BEST/YOU. Summing over test cases gives your final score.
You can find more information about the graph sampling and generation here.   Definition   Class:  Epidemic  Method:  init  Parameters:  int[], int[], int, int, int, int, double, double, double, double  Returns:  int[]  Method signature:  int[] init(int[] g, int[] risk, int infection, int inoculation, int edgeReduce, int K, double X, double Y, double plow, double phigh)    Method:  day  Parameters:  int[]  Returns:  String[]  Method signature:  String[] day(int[] infected)  (be sure your methods are public) 
    Notes    Trying to inoculate a person twice or reduce an edge twice will incur twice the cost, with no added benefit.    Once a person is inoculated or an edge reduced, it remains in that state till the end of the simulation.    If a person becomes infected, he will never again be infected, and will only spread the epidemic on the day immediately after infection.    If u and v are both infected on day D, and both are friends with w, then w will have two, independent chances to get infected on day D+1.    People inoculated before the start of the simulation will have no effect on the seed group chosen to start the simulation.    The memory limit is 1024M and the time limit is 20 seconds per test case.    To understand the effect of K, imagine the case where X=0. If K=0, you could stop the disease by inoculating all the friends of people infected on the day you learn of their infection. If K=1, you would have to inoculate all the friends of friends of people infected on that day.    You will only be given the edges once. Thus a graph with two connected nodes could be represented by {0,1} or {1,0}.    All random choices are uniform and independent.   Constraints    K will be 0, 1 or 2.    X and Y will be in [0.05,0.5).    infection will be in [500,5000].    inoculation will be in [100,1000].    edgeReduce will be in [50,150].    The graph will contain between 100 and 100,000 nodes.   Examples  0)    infection= 1183
inoculation = 740
edgeReduce = 121
K = 0
X = 0.31506782918463455
Y = 0.22966148016863863
p_{low} = 0.280553917185094
p_{high} = 0.9159232446217902
 100 nodes, 208 edges, 2 nodes initially infected 

 1)    infection= 2331
inoculation = 309
edgeReduce = 129
K = 0
X = 0.24815966181513233
Y = 0.06152609613954225
p_{low} = 0.61915118868232
p_{high} = 0.6265059176199126
 1000 nodes, 4047 edges, 7 nodes initially infected 

 2)    infection= 2807
inoculation = 891
edgeReduce = 85
K = 1
X = 0.4176383619072133
Y = 0.10385742808532225
p_{low} = 0.429655474301043
p_{high} = 0.8522529103651292
 10000 nodes, 33103 edges, 7 nodes initially infected 

 3)    infection= 501
inoculation = 813
edgeReduce = 150
K = 0
X = 0.44220946947987716
Y = 0.12823522743365345
p_{low} = 0.24419978107506637
p_{high} = 0.4332017073338966
 100000 nodes, 670755 edges, 3 nodes initially infected 

 4)    infection= 2353
inoculation = 442
edgeReduce = 139
K = 0
X = 0.24499944535060497
Y = 0.07186938430993481
p_{low} = 0.711651651743351
p_{high} = 0.9238667101468845
 39932 nodes, 1400453 edges, 108 nodes initially infected 

 5)    infection= 699
inoculation = 652
edgeReduce = 100
K = 0
X = 0.49263715651162626
Y = 0.3286317821888024
p_{low} = 0.8190145293608756
p_{high} = 0.8794922843679077
 93461 nodes, 1411106 edges, 13 nodes initially infected 

 6)    infection= 4253
inoculation = 854
edgeReduce = 144
K = 1
X = 0.21345433282603826
Y = 0.187625374878841
p_{low} = 0.6280224192300305
p_{high} = 0.9075078847886737
 31355 nodes, 137044 edges, 5 nodes initially infected 

 7)    infection= 1945
inoculation = 591
edgeReduce = 84
K = 2
X = 0.2346685792853087
Y = 0.27770621333496587
p_{low} = 0.3165917779909993
p_{high} = 0.540334947695794
 61652 nodes, 671231 edges, 15 nodes initially infected 

 8)    infection= 2420
inoculation = 923
edgeReduce = 85
K = 2
X = 0.35440044871017784
Y = 0.4243994763629743
p_{low} = 0.3660937966336665
p_{high} = 0.630585328081465
 58852 nodes, 2257029 edges, 16 nodes initially infected 

 9)    infection= 4174
inoculation = 686
edgeReduce = 81
K = 1
X = 0.17275619766273867
Y = 0.059632180201209556
p_{low} = 0.6295556406256922
p_{high} = 0.8184365514653321
 70943 nodes, 2698437 edges, 4 nodes initially infected 


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.

