PROBLEM LINK:
DIFFICULTY
HARD
PREREQUISITES
Graph Theory, All Pair Shortest Paths, Minimum Cost Flow, Binary Search
PROBLEM
You are given a directed graph G of cities. You select some paths on the graph, and cost is calculated as follows
- Add the edge cost for all the edges in the path
- For all paths that are not a cycle, add C
- For all cities that are not touched by any path, add C
EXPLANATION
First, let us make the problem easier. In the original problem a city can be visited by more than one hero and may be visited by the same hero more than once. We wish to simulate paths of heroes that might be using the same set of edges to connect different cities; at the same time making sure that we don’t accidentally start marking some cities that would have been visited as un-visited.
We augment G by adding edges between all pairs of vertices; the cost of these edges is equal to the cost of the minimum cost paths between the vertices. Two heroes may now traverse along these paths.
We apply the restriction that two heroes must visit mutually exclusive cities.
We can easily see that any configuration of paths with mutually exclusive vertices in this new graph will correspond to a valid path traversal in the original graph.
Also, any configuration of paths of heroes will map to a configuration in the new graph where two heroes don’t touch the same vertex.
Note that although there exists a single edge between each pair of vertices of the smallest weight, we will be using minimum cost maximum flow algorithm to ensure that we mark as many cities that can be marked as visited by the hero to reduce paying redundant “C” for cities that remain unvisited.
Now, the problem reduces to finding a min cost path cover of the graph.
- We choose a set of edges from the graph.
- For each vertex, the number of edges starting from that vertex can be at max 1
- For each vertex, the number of edges ending at that vertex can be at max 1
The min cost path cover can be found by using a reasonably efficient Minimum Cost Maximum Flow algorithm on the graph T, such that
- There are 2N + 2 vertices in T
- One source
- One sink
- Two sets of N vertices each
- One set of N vertices is connected to the source with edge capacity 1 and edge weight 0 (Let this be set A)
- Another set of N vertices is connected to the sink with edge capacity 1 and edge weight 0 (Let this be set B)
- For all the edges (u, v) in the given graph, we draw an edge from u in A to v in B with capacity 1 and edge weight equal to the cost of the edge.
A minimum cost maximum flow will be the minimum cost path cover in G. You can verify this intuitively by trying it on a small example.
Now after k successful augmentations, we will have a graph T in which we are routing k units of flow through T. That means, we would have matched k vertices from A to k vertices from B. For vertices that are not yet matched in B, we note that
- either there was no path that started from that vertex in A - which means we pay C to the citizens of this city
- there was a path that started from that vertex in A - which did not end at the same vertex, due to which we pay C to teleport the hero back
- Note that all vertices that are matched can be ignored, since the vertices for the starting points of the respective paths will contribute C to the cost if the hero did not return to the starting vertex
Thus, we want to keep adding a unit of flow one by one. Let c[k] be the cost of introducing the kth unit of flow. If c[k] is larger than C, then we know it is better to compensate the cities than to introduce another hero.
The problem is that doing this one by one might be too slow (since k can be as large as n). But we also know that the marginal cost of each unit of flow is larger than the previous unit of flow.
Formally, c[0] = 0 <= c[1] <= c[2] ... <= c[k]
Hence we can pre-calculate the array c (and the cumulative sums of prefix of c, called cc), and then given C we can binary search on c to find from which unit of flow onwards, is it better to compensate instead of add new flow (or heroes). If such a point comes out to be i, then the answer is
∑t=0 to ic[t] + (n-i)*C
or cc[i] + (n-i)*C
The overall algorithm looks like
- Floyd Warshall for all pair shortest paths - O(N3)
- Min Cost Flow - O(N3 log N + K log K) or O(N3 log N + K log N)
- Finding answers for each year - O(Q * log K)
SETTERS SOLUTION
Can be found here
TESTERS SOLUTION
Can be found here
ACKNOWLEDGEMENT
I owe cgy4ever for having written such an amazing writeup explaining his solution to the problem. The entire editorial is mostly copy pasted from his ideas!
You can view his writeup here.