In some problems it is possible to identify some structure in the optimal solution and then we can brute-force on the unknown parts of that that structure for find the optimal solution.

To illustrate this we are going to solve problem E from BAC 2014.

Pickup and Delivery

A futuristic pickup and delivery company is considering the use of translocators in their business. A translocator is a device that allows the user to teleport himself. It has the two following functions:

• Destroy the current portal if one exists and create one at you current location.
• Teleport yourself to the portal. The portal is destroyed.

Note that this means that there can only be one portal at a given time. Both these actions are instantaneous and take no time to execute.

Given an undirected graph with up to \(50000\) nodes representing road network, the location of the company headquarters H, the pickup location P and the delivery location D, they would like to know what is the minimum time it takes to go from H to P and then to D knowing that you have a translocator available.

Note that you can use the translocator any number of times.

Example:

Suppose the map is given by the following graph.

The best solution is to go from \(H\) to \(D\) and drop the translocator. Then go to the pickup location \(P\), pickup the goods and then teleport yourself back to \(D\). The total time will be \(4\).

Solving the problem

Since the number of nodes can be up to \(50000\), it seems to indicate that there should be a linear time solution for this problem.

We need to reason about the structure of the solution. What can we say about the usage of the translocator? Let's analyze the structure of an optimal solution when the translocator is used.

Consider the following figure. It represents the structure of a path with one teleportation. Going from the headquarters \(H\) to some node \(T\) where we drop the teleporter then to some other node \(X\) and from there, teleport back to \(T\).

(The wiggly arrows represent arbitrary paths)

Clearly, the cycle \((T, \ldots, X, T)\) a waste of time if we did not pass by the pickup location \(P\) because it achieved nothing, we just spent some more time to get back to \(P\).

Therefore the path must have the form:

Here again, we can see a useless path: \((P, \ldots, X, T)\) is useless since if we wanted to go back to \(T\), we could have just teleported from \(P\) to \(T\) directly. Thus, so far, the optimal path will look like this:

The only thing that remains is to go deliver the goods to \(D\). For the same reason as above, this path will never use a teleport as it would just create a cylce where no progress towards reaching \(D\) is achieved:

(We put in gray the parts of the solution that we already know are optimal)

Therefore, we can conclude that an optimal solution that uses the teleporter will look as follows:

In words, we go from the headquarter \(H\) to some node \(T\) where we drop the translocator. Then we go to pickup at \(P\), teleport back to \(T\) and go to \(D\) without teleporting.

So we have the structure of the optimal and the only unknown is node \(T\). Thus one solution is to simply brute force over all possible values of \(T\), evaluate the cost of that solution and find the minimal one.