## 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 (**q**_{1}, ..., q_{n}), the
expected time will be **1/R(1, q**_{1})+1/R(q_{1},
q_{2})+...+1/R(q_{n}, 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**.