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!
Can you provide a link? It seems really interesting
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.
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.