May 22, 2018 On TCO18 Warsaw Lightning Marathon

The Warsaw Lighting Marathon competition featured a task that can be called classical at least by 50%. However, given the scoring formula used to grade solutions, the competition involved by far less randomness than the following Round 1. By the way, the feedback I received from fellow bloggers on the Round 1 analysis draft was the main motivator for me writing this follow-up about the contest that is now back in the past.

Map [Re-]Coloring

Let me remind you the task first. This is needed more for me than for you, because I dived into the Steiner Trees during the last week and almost forgot about the Graph Coloring.
You are given a matrix R having integer elements in range [0, N) and another matrix C having integers in range [0, 4). The task is to return a matrix A with integers in range [0, K) provided K ≤ N so that for p, q ∈ { -1, 0, +1 }, |p+q|=1, we want (R[i, j] ≠ R[i+p, j+q]) ⇔ (A[i, j] ≠ A[i+p, j+q]) and (R[i, j] = R[i+p, j+q]) ⇔ (A[i, j] = A[i+p, j+q]). The objective function is K∙∑min(1, |A[i, j] – C[i, j]|) and we have to minimize it.
Enough pretending I am clever. Here is a picture of what I mean:

Actually this is a picture of what we were given in the seed #1, perhaps the easiest out of what is possible to get as an input in this task. The visualizer generated the following picture of my final solution’s output for this seed:

As you can observe, the cells with the same numbers – regions – must have the same color, and neighbor cells with different numbers must have different colors. You can not and do not have to use more colors than there are regions, obviously.

Reduction

There is a classical task in Computer Science that scientists call Graph Coloring Problem. The problem is NP-complete. For small amount of vertices N it can be solved either exactly, or a good approximation can be found.
Now the question is how to connect the task given in the Warsaw Round this year to the Graph Coloring. We will call it to reduce the problem. Once we found a reduction, we may use any of the known algorithms for the corresponding classical problem, to solve the Lighting Round task.
Let us start with the basic questions. How many neighbor regions a connected region of a map can have? May a region have holes? What about enclaves?
There is a positive answer to the later two questions, but the former one is more tricky. In theory, we can construct a map artificially in a way that there will be each region connected to each other, so the answer to the question is N. However, this is a good answer only for SRM/Algorithm competitions, where you are interested in the worst cases only. For Marathon kind of competition the average case is of great importance. In this particular instance the average value of maximal amount of neighbors a region may have for larger cases was roughly in range [32, 40].
The idea of getting rid of the pixels and the map and starting to work with a graph of regions instead, comes naturally. So once again, let us store a graph, with vertices being connected regions of the same ID, and edges connecting the regions that share a cell side in the colored map given.
Here is a picture of what I mean:

Here, only edges from vertices in 0, 1, 2, 3, 4, and 5 are shown, for simplicity. You are suggested to add the other edges as an exercise.
This reduction can be done in O(S2) time.

Greedy Graph Coloring

After reading through a few documents on the Graph Coloring task and finding a brief mention that one of the approaches involves Simulated Annealing, that was the way to go for me.
Although the general idea was clear, the implementation is worth mentioning. The first thing to do was to embed the tester source code in C++ so that the testing code does not slow down the testing process. I mean the main part of the runtime should be spent in the solution, not in the validation or the test case generation. Note that only the evaluating part was rewritten, and the generated seed data was saved by redirecting the standard output of the tester into a file.
After that was accomplished, an easy, neat and correct Greedy solution for graph coloring was implemented, along with the reduction to the classical task. The idea of the greedy is very basic. I will provide a pseudocode.

GreedyGraphColoring(
	N : int,
	NInitColors : int,
	Neighbors : ref int[][],
	Recolorings : ref int[][])
Begin
	Let N be the number of nodes in a graph
	Let Neighbors represent the edges in the graph,
    	in a form of Adjacency Lists,
    	so that Neighbors[i] is an array of vertices
    	connected to vertex i
	Let NInitColors be calculated outside and represent
    	the amount of colors on the original map
	Let Recolorings be precalculated array, so that
    	Recolorings[I][Color] = number of recolorings
    	needed to repaint region I into color Color completely
	Assign NConnectedNeighbors = new int[N]
	Assign Result = new int[N]
	Fill Result with a stub value, let it be -1
	Assign NColors = 0
	Assign NRecolorings = 0
	Let NBest = 7 be a magic number of best edges we will select from
	Assign Visited = new bool[N]
	Fill Visited with value False
	Assign StartRegion = Random number in range [0, N)
	Assign Stack = new int[N]
	Assign Stack[0] = StartRegion
	Assign Visited[StartRegion] = True
	For I in Range [0, N)
    	Call GreedyGraphColoringIteration(
        	Depth, NBest, StartRegion, N, NInitColors, NColors, NRecolorings,
        	Visited, Stack, ConnectedNeighbors, Neighbors, Recolorings, Result)
	Return Result
End
GreedyGraphColoringIteration(
	Depth : ref int,
	NBest : int,
	N : int,
	NInitColors : int,
	NColors : ref int,
	NRecolorings : ref int,
	Visited : ref bool[],
	Stack : ref int[],
	ConnectedNeighbors : ref int[],
	Neighbors : ref int[][],
	Recolorings : ref int[][],
	Result : ref int[])
Begin
	Assign I = Random number in range [0, Min(NBest, Depth))
	Assign X = Stack[I]
	Remove item X from Stack for instance, by doing
	Stack[I] = Stack[Depth - 1]
	Depth--
	For Each Y in Neighbors[X]
    	If Not Visited[Y]
        	Stack[Depth] = Y
        	Visited[Y] = True
        	ConnectedNeighbors[Y]++
        	Depth++
	PartialSort(Stack, Min(NBest, Depth),
           Comparing Descending (Neighbors[A].Length - ConnectedNeighbors[A]))
	This will partially sort the Stack so that the first
    	NBest elements of it will be the best according
    	to the comparison function provided
	Assign UsedColor = new bool[NColors]
	For Y in Neighbors[X]
    	If Result[Y] != the stub value -1
        	Assign UsedColor[Result[Y]] = True
	For Color in Range [0, NInitColors)
    	If Not UsedColor[Color]
        	If Result[X] = -1 Or Recolorings[X][Color] < Recolorings[X][Result[X]]
            	Assign Result[X] = Color
	If Result[X] = -1
    	Assign Result[X] = NInitColors
    	While UsedColor[Result[X]]
        	Result[X]++
	NColors = Max(NColors, Result[X] + 1)
	NRecolorings += Recolorings[X][Result[X]]
End

The idea is to call this greedy procedure a few thousand times, while updating the best so far solution and its scores.

Local Search

A major improvements would be to try to improve the best solution found by the greedy algorithm. This can be done by a Local Search.
The idea is to try to get rid of a color with maximal ID, ie. the one that was added the last in the greedy solution. This will reduce the amount of colors used, and potentially improve the overall score of a solution.
The local search iteratively recolors a semi-random vertex that is currently colored into a color with maximal ID. It invalidates all the neighbor region colorings if they are broken (have the same color as the new color of the repainted vertex). If the “semi-randomness” is good enough, this will converge quickly, if the solution exists. We use a cutoff by timeout to exit even if no improvement was found.
The question is how to make this “semi-random” selection of a vertex to recolor out of all the vertices that have the color with highest ID? What color to assign to it? During the match I just used a uniform distribution to solve both questions. As pointed out by Nika Jimsheleishvili (aka. nika), the color selection can be done greedily, by choosing the color that is least frequent between the recolored vertex’ neighbors.

Simulated Annealing

The last phase was to apply the SA metaheuristic to the best solution found by the Greedy part and improved by the Local Search.
The update step for me was simply changing the color of a region to some other random color. Jaco Cronje (JacoCronje) said that swapping colors of neighbor vertices worked better for him. This turned out to be a known solution, called Kempe chain. Jaco also wrote an article discussing a similar problem – MapMaker – back in 2006.

Other Improvements

Once you have a working solution with these three phases, refer to the after-match discussion to get some more inspiration for improvements.

Conclusion

I would like to thank Mariia Mykhailova for the visualizer – I have used the pictures generated by her visualizers in many of my blog posts, now is the time to give her the credit. Thank you the reader – for waiting patiently for this analysis.
The funny thing about this match is that I used the visualization the first time while writing this blog post. And it was great to solve the task in an open air at my countryside. Unfortunately I was not able to attend the onsite Warsaw event because of repairing that same countryside house, so I would like to greet those who I know in person, and who were there last year and/or this year – Magdalena, Przemyslaw, Marek, Marcin, Ania, Krzysztof, Mateusz! Another hello goes to Harshit for writing an overview of the event!