PROBLEM LINK:
Author: Tiancheng Lou
Tester: Jingbo Shang
Editorialist: Ajay K. Verma
DIFFICULTY:
CHALLENGE
PREREQUISITES:
Bipartite matching, Hungarian algorithm
PROBLEM:
Given a grid with some cells colored black and others white, the task is to trasform the grid into one where all black cells are connected, using minimum cost transformations. A single transformation can change the color of a single cell, or swap the colors of two adjacent cells. The cost of a swapping transformation is 1, while the cost of changing the color of a cell to black (white) is c2 (c3).
QUICK EXPLANATION:
If the target grid, as well as the cells whose colors have to be changed are already known, then the problem reduces to transform a source grid configuration into a target grid configuration using only swapping operations. This can be solved using a min-cost matching algorithm. Hence, the main task is to find the target grid and the cells whose color should be changed. This can be done either using a greedy heuristic or using a simulated annealing kind of algorithm.
EXPLANATION:
First, let us ignore the costly transformations of changing the color of a single cell, and assume that the only allowed transformation is to swap the color of two adjacent cells. Furthermore, let us assume that some oracle already found the target grid configuration for us (we will discuss later how to implement this oracle). This means that we have a source grid configuration, and a target grid configuration (from oracle), and we want to find out how to transform the former into the latter using minimum cost transformations.
Let the black cells in the source configuration be at positions A1, A2, …, An, and in the target configuration be at positions B1, B2, …, Bn. After applying the swapping transformations each of the Ai’s will be mapped to exactly one of the Bj. In other words, the problem is equivalent to find a minimum cost matching between the set of Ai’s and Bj’s.
The number of transformations to move the color of a cell at position A (x1, y1) to a cell at position B (x2, y2) is the same as the L1-distance between the two points, i.e., abs(x1 - x2) + abs(y1 - y2).
Hence, we can create a complete bipartite graph G = (U, V, E = (U x V)), where the vertices on the left side correspond to the cell Ai’s, and the nodes on the right side correspond to the cell Bj’s. The weight of the edge between Ai and Bj is the L1-distance between their cell positions.
One could use Hungarian algorithm to compute the min-weight matching, however it takes O (n3) time, and will run out of time. Hence, we need to use some heuristic to solve the problem approximately. One possibility could be start with a random matching and then use the path augmentation only a bounded number of times. Other possibility could be to start with a random matching and then swap the pair of matched edges when beneficial, i.e., if a matching has Ai matched to Bi and Aj matched to Bj, while c (Ai, Bi) + c (Aj, Bj) > c (Ai, Bj) + c (Aj, Bi), then we should match Ai with Bj and Aj with Bi.
Finding the Target Configuration:
In the previous section we have assumed that the target grid configuration is already known. In this section we will discuss how to find a “potential candidate” for the target configuration.
There are two main constraints:
- In the target configuration, all black cells must be connected, and
- Number of black cells in the target configuration should be the same as the number of black cells in the original configuration.
Ideally, We would also like a target configuration, which is not “too far away” from the source configuration. Basically, we can pick a pivot cell, and then move all the black cells to this pivot cell, until they form a connected graph. This can be done using Dijkstra’s algorithm
For example, let us assume that the position of black cells in the original grid were at position (0, 0), (1, 2), (1, 6), (3, 4), (3, 9), (5, 8), and we pick (3, 4) as a pivot point, then the process will follow as follows:
(3, 4) is already occupied, we have four locations, where a black cell can be moved so that it is connected to the so far constructed connected component. These locations are (2, 4), (5, 4), (3, 3), and (3, 5). Among these (3, 3) is closest to the any of the un-moved cells. Hence, we move (1, 2) to (3, 3).
Now, connected component has two cells (3, 4) and (3, 3). The free locations are (3, 2), (3, 5), (2, 3), (2, 4), (4, 2), (4, 4). Since (0, 0) is closest to (3, 2), it should be moved there.
The same process continues untill all black cells are moved to form a connected graph. The location of pivot is arbitrary. Ideally, the center of the grid should be the best location. However, if all the black cells are concentrated to one of the corners, then that corner might be a better choice. Once could try the center as well as the four corners of the grid as pivot, and pick the one which gives the best results.
Addition/Removal of Black Cells May Help
So far we have considered only the swap transformation. The operations of changing the color of a cell (or equivalenly addition or removal of black cells) are more expensive than the swapping transformation. However, they could be beneficial in some cases. If one black is too far away from the other set of black cells, which are close to one another, then it is better to remove the far away black cell rather than moving it to form a connected component.
These addition and removal transformation can be used as a secondary optimization. Compute the min-cost matching based on only the swap transformations, then iterate through the edges of the matching in decreasing order of the cost. If the cost of an edge is more than the cost of a remove transformation, and removing the corresponding cell from the traget configuration does not make it disconnected, then remove that cells corresponding to this edge from both source and target configurations. In a similar way, if the weigt of an edge (A, B) is more than the cost of add transformation, and it is possible to add a cell C to the target configuration while keeping it connected such that the c (A, C) < c (A, B), then one should add the cell A in the source configuration and C in the target configuration. The addition and removal process can be further tuned as seen in the setter’s solution.
After doing these addition and removal transformations, the min-cost matching is applied again followd by possible addition and removal transformations. The process is repeated until the cost improves, or we run out of time.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.