Subtask 1

For subtask 1, we can simulate the expansion process as described in the problem. For each of the ~\mathcal{O}(NM)~ blank pixels, we can loop through all ~\mathcal{O}(NM)~ coloured pixels to find the closest pixel, breaking ties by the colour number. This takes ~\mathcal{O}(N^2M^2)~ time overall.

Time Complexity: ~\mathcal{O}(N^2M^2)~

Subtask 2

Subtask 2 was primarily created to reward subtask 3 solutions that do not correctly break ties by the colour number.

Alternatively, we can note that each coloured pixel "covers" a tilted square region, and it suffices to simply find whether each pixel is covered or not when all the colours are the same. We can do this in ~\mathcal{O}(NMK)~ time using a difference array for each row. For each coloured pixel, loop through the ~K~ rows closest to it and add ~1~ to the subinterval of this row that is covered by the expanded region of this pixel. A pixel is coloured in the final drawing if the number at this pixel is greater than ~0~ after all the updates.

Time Complexity: ~\mathcal{O}(NMK)~

Subtask 3

For subtask 3, we can simulate the expansion process in ~K~ iterations. In each iteration, consider all currently blank pixels and check if one of its ~4~ neighbouring pixels is coloured. If so, we colour this pixel with the colour of the smallest-numbered neighbour. This takes ~\mathcal{O}(NMK)~ time overall.

Time Complexity: ~\mathcal{O}(NMK)~

Subtask 4

Subtask 4 was primarily created to reward full solutions that do not correctly break ties by the colour number.

Alternatively, we can rotate the grid by ~45^{\circ}~ and use 2D difference arrays to update the covered area of each coloured pixel, similar to subtask 2.

Time Complexity: ~\mathcal{O}(NM)~

Subtask 5

For subtask 5, we can perform a simultaneous BFS from the coloured pixels. During the BFS, each node stores the distance to the nearest coloured pixel as well as the colour of the smallest-numbered nearest pixel. In order to break ties by the colour number properly, whenever we find a different path to a node with the same distance but smaller-numbered source pixel, we update the nearest colour stored for this node. Note that it is not necessary to push this node into the queue again, as this node will always still be in the queue when this happens.

Other ~\mathcal{O}(NM\log(NM))~ approaches are possible, including:

• Sorting the coloured pixels by their number initially and pushing them into the BFS queue in that order. This ensures that the first path we consider to a node has the smallest-numbered source pixel, so a normal BFS works from here.
• Performing a grid traversal that more closely resembles Dijkstra's algorithm, using a priority queue to break ties by the colour of the source pixel.

Time Complexity: ~\mathcal{O}(NM)~ or ~\mathcal{O}(NM\log(NM))~