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 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.
    1. To be precise, there are 101^3 = 1030301 possible colors since colors are in the range [0, 100] but that is not a big deal.
    2. 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.
    3. 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<=index<=n). Basically, each node in the queue has to store (R%, G%, B%, index).
    4. Technically, we could BFS either starting from the n types of wools he has or the 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 types of wool to the queue in the order given. This way, we can ensure that we can get the lowest index.
    5. We might be able to use a 101^3 graph but to save time, we can store the max dimension among all the n wools and the q queries. This way, we just have to fill in the max_dimension^3 amount of the graph, which could save time. This explains the time complexity including "max(x_i, y_i, x_i, X_i, Y_i, X_i)^3".
    6. The +q in the time complexity just stands for the q queries which can be found in constant time by just indexing the 3D vector we stored all the information in.