Problem Statement | |||||||||||||
| We can think of a computer network as a undirected graph where nodes
represent routers and edges represent connections between the routers.
In this network, there are a number of packets, each of which has a
source and a target. Over a number of discrete time steps, each
packet must travel from its source to its target. During one time
step, a packet at router u may move to router v, if
there is a link between u and v. However, only one
packet may use a link between u and v during a
particular time step (if one packet uses a link to go from u
to v, no other packet can use that link to go from v
to u during the same time step). The problem is to figure
out the best way to route the packets through the network so that they
get to their destinations as soon as possible.
You will be given an int, 2<=N<=100, representing the number of nodes in the graph. A String[], g will specify the edges (up to 4950 of them), where each element is of the form "u v", where u and v are distinct integers between 0 and N-1, inclusive, indicating an edge between node u and node v. There will be at most one edge between a pair of nodes. A String[], packets, will specify the packets to be sent in the network, where 10<=|packets|<=2,000. Each element will be formatted as "s t", indicating a packet with source s and target t, where s does not equal t. These graphs will be randomly generated as described at the end of the problem statement. Furthermore, the graphs will be connected. Your task is to come up with a routing plan for the packets through the network. You should return a String[], each element of which represents the locations of the packets after each time step. Each element of the String[] should be a space delimited list of the packets' locations at a time step corresponding to the index of the element (the first element of the return corresponds to the locations of the packets after the first time step). The list should give the locations in the same order that the packets are given to you. For example, consider the simple network with 2 nodes and 2 packets: N=2 g={"0 1"} packets={"0 1","1 0"} In this case, there are two packets trying to go in opposite directions along the one link. One possible return would be: {"0 0","1 0"} This indicates that in the first time step, the second packet moves along the link from node 1 to node 0. Since that link is in use, the first packet cannot also use it, so during the second time step, the first packet moves from node 0 to node 1, and at this point all packets have reached their destinations. Another valid return would be {"0 1","1 1","1 0"}. In this return, none of the packets moved during the first time step. While valid, this is clearly suboptimal. Your program will be scored based on the quality of your method's return, and the time it takes your method to execute. If your method's return is invalid in any way or if not all the packets reach their destinations, you will get a 0. Otherwise, your score for a test case will be given by: quality2 - 10 * execution time (quality is defined below, time is in seconds)If the quality or the above formula turns out to be negative, the score is set to 0. Your overall score will be the sum over all test cases of SCORE/OPT, where OPT is the highest score anyone has achieved on a test case (0/0 = 1 here). Thus, if you score 10 on one test case, and someone else scores 20 on the same test case, you will get 10/20 = 0.5 towards your final score for that test case. The quality term used above will be the percent improvement of your solution over a naive solution that routes packets over a random shortest path. In the naive solution, if a packet is being routed to node v, and is currently at node u, then a node is chosen at random out of all nodes that are on some shortest path from u to v and are also connected to u. The packet will eventually be sent from u to that node, with conflicts along the link resolved by letting a random packet use the link. Finally, there are dozens of realistic and interesting classes of graphs that could be randomly generated and used here. One class that has drawn a great deal of interest in recent years is ad-hoc networks. To simulate these graphs, we will first select a random value for N, the number of nodes. Each node will then be assigned a random x and y value in a cartesian plane, at a distance of no more than 50 from the origin. Then, we will select random values for the lower and upper bounds on each node's range (5<=lower<upper<30). Each node will be assigned a range uniformly between these bounds. Two nodes will be able to communicate if their distance from each other is less than both their ranges. If the network generated is not connected, it will be scrapped and a new attempt will be made. Otherwise, a random number of packets will be generated, the sources and sinks of which are random. Here is pseudocode to generate a graph. The notation [x,y] indicates a random value between x and y, inclusive (the value is floating point unless an integer is clearly required). Roughly 30% of generated graphs are connected.
N = [2,100]
lower = [5,30]
upper = [5,30]
if(upper < lower)swap(lower,upper)
for(i = 0 to N-1){
do{
x[i] = [-50,50]
y[i] = [-50,50]
}while(x[i]*x[i]+y[i]*y[i] > 50*50);
r[i] = [lower,upper]
}
for(i = 0 to N - 1){
for(j = 0 to i-1){
if(dist(i,j) < range[i] && dist(i,j) < range[j]){
connected(i,j) = connected(j,i) = true
}
}
}
M = [10,2000]
for(i = 0 to M-1){
do{
packets(i,0) = [0,N-1]
packets(i,1) = [0,N-1]
}while(packets(i,0) == packets(i,1));
}
| |||||||||||||
Definition | |||||||||||||
| |||||||||||||
Notes | |||||||||||||
| - | The time limit is 20 seconds. | ||||||||||||
| - | The memory limit is 1 gigabyte. | ||||||||||||
| - | The thread limit is 32. | ||||||||||||
| - | There may be multiple packets corresponding to a single pair of nodes. | ||||||||||||
| - | To reduce variance, the naive algorithm explained above is run 5 times, and the median number of steps is used for comparison. | ||||||||||||
Examples | |||||||||||||
| 0) | |||||||||||||
| |||||||||||||