IPSC Logo

Internet Problem Solving Contest

IPSC 2007

Solution to Problem I – Internet is Faulty

Build a graph where the vertices will be computers and weights of edges will be the probabilities from the input. Run the Floyd-Warshall algorithm. In the algorithm don't add the probabilities together, but multiply them. As a result for each two computers u, v in the internet we now know the probability R(u, v) that a packet succesfully gets from computer u to v using the best possible sequence of links (without using any temporary storage).

In this problem we used Geometric distribution as our probability model. The expected time for one packet and a route with a probability p is 1/p. The expected time for transferring a file of size S is S/p. If we use one account and the first part of the route has probability a and the second part has probability b, the resulting expected time is 1/a+1/b. If we transfer file from computer 1 to 2 and use accounts on more computers (q1, ..., qn), the expected time will be 1/R(1, q1)+1/R(q1, q2)+...+1/R(qn, 2) (you can find the definition of R(u, v) above). Because we want to minimize this expected time, we run another Floyd-Warshall algorithm. The weight of an edge between computers u and v will be 1/R(u, v). As a result we have the shortest route between each two computers and we can calculate the result – it's the length of the shortest path between 1 and 2 multiplied by the file size S.