Editorial for CCC '18 S5 - Maximum Strategic Savings
Submitting an official solution before solving the problem yourself is a bannable offence.
To rephrase the problem - imagine that we have a graph on a 2D grid with rows and columns. For notational convenience, we'll denote a horizontal repeated-edge as a pair of columns, and a vertical repeated-edge as a pair of rows. We're given horizontal repeated-edges and vertical repeated-edges. For every horizontal repeated-edge, we construct edges, one in every row, connecting the vertices in the columns in that row. Similarly, for every vertical repeated-edge, we construct edges, one in every column, connecting the vertices in the rows in that column. We wish to remove a subset of edges of maximal weight while still allowing the graph to be connected.
We first claim that this problem is equivalent to finding the weight of the minimum spanning tree on the given graph. Assume that there is a spanning tree of this graph of smaller weight than the one that is left by removing the desired subset - note that if we consider the edges that aren't present in the spanning tree, that subset would have higher weight than our claimed maximal-weight subset. This is a contradiction.
Consequently, instead of thinking about the problem in terms of removal of edges, we'll think about it as a problem about constructing the minimum spanning tree.
For 2 marks, every edge in the graph has unit weight. If the graph has nodes, its spanning tree has edges all of unit weight. Consequently, we can compute the answer without even reading the specifics of the edges because the problem guarantees the graph is connected.
For an additional 2 marks, we have that and are less than or equal to 200. We claim that and must be less than or equal to and , respectively. The intuition behind this is that if we have columns, we need horizontal repeated-edges just to connect the columns with each other, since the vertical edges do not help us move from column to column. Therefore, the number of edges in the graph is relatively small - in particular under , so we can compute the minimum spanning tree directly using an algorithm like Kruskal's or Prim's that can compute the minimum spanning tree in , which in this problem is .
For an additional 5 marks, we have that and are less than or equal to 200. Although the number of vertices is low, the number of edges within a given row or a given column can now scale to . In the above analysis, we noted that we needed horizontal repeated-edges just to connect the columns with each other. We can show that we need exactly such horizontal repeated-edges to connect the columns. This means that instead of considering all edges simultaneously, we can compute the minimum spanning trees of the repeated-edges, discard all the repeated-edges that we do not use, and then we're left with solving the subproblem above.
For full credit, we have to leverage the structure of the graph being a 2D grid. If we consider how Kruskal's algorithm works, we start with a set of vertices, all disconnected from each other. We iteratively consider the edges in nondecreasing weight order and add them as long as they do not create cycles within the graph. Therefore, instead of considering specific edges on the graph, we can just consider the repeated-edges. We start out with row vertices and column vertices, all disconnected from each other. Assume without loss of generality that we're considering a horizontal repeated-edge. Check first that the two column vertices it connects are not already connected - otherwise we can ignore this edge. If vertical repeated-edges have been added to the minimum spanning tree, then there are disjoint components where we can add horizontal edges, which informs us of how many edges we can safely add. Finally, note that the column vertices are now connected using a data structure like union-find. Iterate over all repeated-edges until the entire graph is merged, which is done with vertical repeated-edges are added and horizontal repeated-edges are added. This is .