HaiYen's blog

By HaiYen, history, 2 months ago, In English

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!

 
 
 
 
  • Vote: I like it
  • +10
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you provide a link? It seems really interesting

»
2 months ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.