### HaiYen's blog

By HaiYen, history, 2 months ago,

Hello, can anyone help me with this problem:

Given N rooms (N <= 100), at first, each room was painted by one color (0, 1 or 2). There are N robots, each robot has a set of rooms that we can use to paint all elements in. For an room after painting, its color changes from 0 to 1, 1 to 2 and 2 to 0.

Calculate the minimum times need to use robots to make all the rooms have color 0. (A robot can be used multiple times).

Thanks so much!

• +10

 » 2 months ago, # |   0 Can you provide a link? It seems really interesting
 » 2 months ago, # | ← Rev. 2 →   +1 Let $c_i$ be the color of room $i$ and $t_j$ (at most 2) be the number of times we use $j_{th}$ robot.Then we have $n$ equations:$b_{1,1}t_1 + b_{1,2}t_2 + ... + b_{1,n}t_n \equiv 3 - c_1 \pmod{3}$$b_{2,1}t_1 + b_{2,2}t_2 + ... + b_{2,n}t_n \equiv 3 - c_2 \pmod{3}$...$b_{n,1}t_1 + b_{n,2}t_2 + ... + b_{n,n}t_n \equiv 3 - c_n \pmod{3}$Where $b_{i, j}$ is whether $j_{th}$ robot can paint room $i$.IIRC this can be solved with Gauss elimination.
•  » » 2 months ago, # ^ |   0 Gaussian elimination solves the problem of whether there is a solution, but we need the smallest one. From this point of view it is already an ILP kind of thing. Sometimes ILP could be reduced to simple LP, but I don't think it is possible here, because if we have three robots $(1, 2)$, $(1, 3)$ and $(2, 3)$ and we want them to paint all three rooms exactly once, the best LP-solution would be $(0.5, 0.5, 0.5)$ which gives us a definitely fractional result of $1.5$ moves.So, ILP approach should not work from theoretical perspective, but it may work on practice. Moreover, I do think that modern ILP-solvers can solve this kind of instances sufficiently fast. Also, I think that there are some ways to reduce the size of the ILP instance, so that we would have to run the solver on only $50$ equations instead of $100$ or so.