Editorial for CCC '18 S5 - Maximum Strategic Savings


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Authors: xiaowuc1

To rephrase the problem - imagine that we have a graph G on a 2D grid with N rows and M 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 P horizontal repeated-edges and Q vertical repeated-edges. For every horizontal repeated-edge, we construct N edges, one in every row, connecting the vertices in the columns in that row. Similarly, for every vertical repeated-edge, we construct M 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 NM nodes, its spanning tree has NM-1 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 P and Q are less than or equal to 200. We claim that N and M must be less than or equal to P+1 and Q+1, respectively. The intuition behind this is that if we have M columns, we need M-1 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 10^5, 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 O(E \log V), which in this problem is O((NP+MQ) \log (NP+MQ)).

For an additional 5 marks, we have that N and M 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 10^5. In the above analysis, we noted that we needed M-1 horizontal repeated-edges just to connect the columns with each other. We can show that we need exactly M-1 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 N row vertices and M 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 K vertical repeated-edges have been added to the minimum spanning tree, then there are N-K 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 N-1 vertical repeated-edges are added and M-1 horizontal repeated-edges are added. This is O(P \log P + Q \log Q).


Comments


  • 6
    bqi343  commented on Feb. 24, 2018, 5:19 p.m.

    Basically just USACO fencedin. :(


    • 1
      Riolku  commented on April 15, 2018, 10:33 a.m.

      Although some aspects are similar here, the grid may not be perfect here. Consider if, in this case, there were flights from 1-3, 2-3, and 1-2. This would not be a perfect grid at all! Furthermore, considering the much larger numbers in fencedin, I would imagine that the problems have very different solutions indeed.