Subtask 1

We can do some simple math. If the girl is not in node 1, the CS nerd is guaranteed to find her in node 2. Therefore, we simply need to find the average time to get to node 2 and divide that result by 2 since there is a 50% chance that the girl is in node 1, which takes 0 time, and another 50% chance that the CS nerd has to take a hallway to node 2.

Time complexity: ~\mathcal{O}(M)~

Subtask 2

We need a bit more knowledge on how expected values work. For the CS nerd to reach node 2, let ~f(1,2)~ be the expected time from node 1 to node 2. Also, let ~f(3,2)~ be the expected time from node 3 to node 2. Obviously, ~f(2,2) = 0~.

Then an equation can be created if the CS nerd is simulated to move once from node 1.

$$\displaystyle f(1,2) = p(1,2) \cdot (f(2,2) + time(1,2)) + p(1,3) \cdot (f(3,2) + time(3,2))$$

~p(x,y)~ is the chance that the CS nerd will travel from ~x~ to ~y~.

In this way, 3 equations can be created (an equation is ~f(2,2)=0~). ~f(1,2)~ can be solved, and this is the first linear system.

The girl may be at node 3, so 2 linear systems have to be solved in total. The answer is the average of the three possible times.

Time complexity: ~\mathcal{O}(M)~

Subtask 3

Generate the equations from above. There would be ~\mathcal{O}(N)~ systems to solve in total. Use Gaussian elimination to solve each of these ~\mathcal{O}(N)~ systems, but note that the runtime of Gaussian elimination is ~\mathcal{O}(N^3)~ since a system contains ~\mathcal{O}(N)~ variables. The answer is the average of the ~N~ possible times.

Time complexity: ~\mathcal{O}(N^4)~

Subtask 4

It is important to treat the graph as a Markov chain where each edge contains a probability and a time. The simplest way is to create two matrices containing ~\mathcal{O}(N^2)~ elements.

Observe that a node can be removed from the graph, while maintaining the same expected value. Let the removed node be labelled ~k~, then any edge pointing to ~k~ must exit it somewhere else in the graph. The edge pointing to ~k~ can be replaced by ~\mathcal{O}(N)~ other edges, and the process of combining duplicate edges is left as an exercise. After ~k~ has an indegree of 0, ~k~ can be removed from the graph without changing the expected value to any remaining node in the graph.

There is another bit of cleanup after ~k~ is removed. There may now be ~\mathcal{O}(N)~ selfloops in the graph. Since only edges leading out of a node are important, a selfloop can be cleaned up in ~\mathcal{O}(N)~ time. The implementation is also left to the reader. Therefore, the total time complexity of removing a node is ~\mathcal{O}(N^2)~.

To get the expected time to a specific node, ~\mathcal{O}(N)~ removals must take place. Note that the time complexity of this method is ~\mathcal{O}(N^3)~, which is equal to Gaussian elimination.

The last observation is that by doing ~\mathcal{O}(N^4)~ operations in total, a lot of work is repeated. For example, getting the answer to node 2 and node 3 would require many of the same nodes to be removed, and therefore the time complexity can be improved.

One possible way is to create a divide-and-conquer algorithm that takes in a range ~[L, R]~ and returns the value ~f(1, L) + f(1, L+1) + \dots + f(1, R)~. Notice that half of these nodes can be removed, then the divide-and-conquer algorithm can be called again (after the ~\mathcal{O}(N^2)~ elements in the matrix are duplicated). In this algorithm ~\mathcal{O}(N \log N)~ nodes are removed in total, and ~\mathcal{O}(N)~ matrices are duplicated in total. The implementation of this algorithm is left to the reader as an exercise.

We can make further optimizations to reduce the total time complexity to ~\mathcal{O}(N^3)~ because a divide-and-conquer creates two matrices with half the size. That is, suppose your algorithm takes ~f(N)~ steps where ~f(N) = 2f(\frac N 2) + \mathcal{O}(N^3)~. Then the Master Theorem proves that ~f(N) = \mathcal{O}(N^3)~.

Time complexity: ~\mathcal{O}(N^3)~ or ~\mathcal{O}(N^3 \log N)~