Editorial for Canada Day Contest 2021 - Fine Art

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.

Author: Aaeria

Hint

There are only $101^3 = 1\,030\,301$ ~101^3 = 1\,030\,301~ possible colours.

Hint

Try putting the coordinates on a grid graph.

Solution

Perform a multisource breadth first search from each of the wool colours to find the closest wool for every possible colour. Now the answer to each query has been calculated.

Time complexity: $\mathcal O(\max(x_i,y_i,z_i,X_i,Y_i,Z_i)^3+q)$

Comments

5
suguruchhaya commented on July 13, 2021, 2:53 p.m. ← edited →
What does "the grid" mean? Think of it as a 3D grid/graph. If we add 1% of red, we move in one direction. Adding 1% of green and blue will move you in different directions respectively. Think of this problem as BFS in 3 dimensions. Also, remember that during BFS you can both add and subtract 1% of RGB at every node. I forgot to do the subtracting part initially.

Apart from the BFS queue, store the graph in a 3D vector with all cells initially marked as not visited. During BFS, when you visit a non-visited cell, mark it with the index of the wool you had ( $1 \le \text{index} \le n$ ~1 \le \text{index} \le n~). Basically, each node in the queue has to store (R%, G%, B%, index).

Technically, we could BFS either starting from the $n$ ~n~ types of wools he has or the $q$ ~q~ pixels he wants to build. But since the problem asks to output the lowest index of the closest substitute, it would be better to insert the $n$ ~n~ types of wool to the queue in the order given. This way, we can ensure that we can get the lowest index.

We might be able to use a $101^3$ ~101^3~ graph but to save time, we can store the max dimension among all the $n$ ~n~ wools and the $q$ ~q~ queries. This way, we just have to fill in the $(\text{max dimension})^3$ ~(\text{max dimension})^3~ amount of the graph, which could save time. This explains the time complexity including " $\max(x_i, y_i, z_i, X_i, Y_i, Z_i)^3$ ~\max(x_i, y_i, z_i, X_i, Y_i, Z_i)^3~".

The $+q$ ~+q~ in the time complexity just stands for the $q$ ~q~ queries which can be found in constant time by just indexing the 3D vector we stored all the information in.