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 pv. 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 pv to pv*X, for some constant X. Reducing the probability along an edge also reduces the infection probability to pv*Y, for some constant Y. These two effects are cumulative, so the infection probability can be pv*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 = (pu-plow)/(phigh-plow)
if(p < 0.5 && rand() < 1-2*p) risk = low
else if(p > 0.5 && rand() < 2*p-1) 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 plow and phigh will be chosen by picking two random numbers between 0.1 and 1, and ordering them. Each pv will then be chosen randomly between plow and phigh. 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) | |
| | | Returns:
"infection= 1183<br>
inoculation = 740<br>
edgeReduce = 121<br>
K = 0<br>
X = 0.31506782918463455<br>
Y = 0.22966148016863863<br>
p<sub>low</sub> = 0.280553917185094<br>
p<sub>high</sub> = 0.9159232446217902<br>
" | | 100 nodes, 208 edges, 2 nodes initially infected |
|
|
| 1) | |
| | | Returns:
"infection= 2331<br>
inoculation = 309<br>
edgeReduce = 129<br>
K = 0<br>
X = 0.24815966181513233<br>
Y = 0.06152609613954225<br>
p<sub>low</sub> = 0.61915118868232<br>
p<sub>high</sub> = 0.6265059176199126<br>
" | | 1000 nodes, 4047 edges, 7 nodes initially infected |
|
|
| 2) | |
| | | Returns:
"infection= 2807<br>
inoculation = 891<br>
edgeReduce = 85<br>
K = 1<br>
X = 0.4176383619072133<br>
Y = 0.10385742808532225<br>
p<sub>low</sub> = 0.429655474301043<br>
p<sub>high</sub> = 0.8522529103651292<br>
" | | 10000 nodes, 33103 edges, 7 nodes initially infected |
|
|
| 3) | |
| | | Returns:
"infection= 501<br>
inoculation = 813<br>
edgeReduce = 150<br>
K = 0<br>
X = 0.44220946947987716<br>
Y = 0.12823522743365345<br>
p<sub>low</sub> = 0.24419978107506637<br>
p<sub>high</sub> = 0.4332017073338966<br>
" | | 100000 nodes, 670755 edges, 3 nodes initially infected |
|
|
| 4) | |
| | | Returns:
"infection= 2353<br>
inoculation = 442<br>
edgeReduce = 139<br>
K = 0<br>
X = 0.24499944535060497<br>
Y = 0.07186938430993481<br>
p<sub>low</sub> = 0.711651651743351<br>
p<sub>high</sub> = 0.9238667101468845<br>
" | | 39932 nodes, 1400453 edges, 108 nodes initially infected |
|
|
| 5) | |
| | | Returns:
"infection= 699<br>
inoculation = 652<br>
edgeReduce = 100<br>
K = 0<br>
X = 0.49263715651162626<br>
Y = 0.3286317821888024<br>
p<sub>low</sub> = 0.8190145293608756<br>
p<sub>high</sub> = 0.8794922843679077<br>
" | | 93461 nodes, 1411106 edges, 13 nodes initially infected |
|
|
| 6) | |
| | | Returns:
"infection= 4253<br>
inoculation = 854<br>
edgeReduce = 144<br>
K = 1<br>
X = 0.21345433282603826<br>
Y = 0.187625374878841<br>
p<sub>low</sub> = 0.6280224192300305<br>
p<sub>high</sub> = 0.9075078847886737<br>
" | | 31355 nodes, 137044 edges, 5 nodes initially infected |
|
|
| 7) | |
| | | Returns:
"infection= 1945<br>
inoculation = 591<br>
edgeReduce = 84<br>
K = 2<br>
X = 0.2346685792853087<br>
Y = 0.27770621333496587<br>
p<sub>low</sub> = 0.3165917779909993<br>
p<sub>high</sub> = 0.540334947695794<br>
" | | 61652 nodes, 671231 edges, 15 nodes initially infected |
|
|
| 8) | |
| | | Returns:
"infection= 2420<br>
inoculation = 923<br>
edgeReduce = 85<br>
K = 2<br>
X = 0.35440044871017784<br>
Y = 0.4243994763629743<br>
p<sub>low</sub> = 0.3660937966336665<br>
p<sub>high</sub> = 0.630585328081465<br>
" | | 58852 nodes, 2257029 edges, 16 nodes initially infected |
|
|
| 9) | |
| | | Returns:
"infection= 4174<br>
inoculation = 686<br>
edgeReduce = 81<br>
K = 1<br>
X = 0.17275619766273867<br>
Y = 0.059632180201209556<br>
p<sub>low</sub> = 0.6295556406256922<br>
p<sub>high</sub> = 0.8184365514653321<br>
" | | 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)2020, TopCoder, Inc. All rights reserved.