Internet Problem Solving Contest

IPSC 1999

Solution to Problem F – Panel

We provide correct output files for both input files. There was a different strategy for the easy and difficult input file. While the solution for the easy input could be found by running an exhaustive search, the difficult one needed a bit trickier approach.

The easy data set.

First of all, observe that if you flip all swiches, each bulb turns once on and once off (or off and on), so nothing happens. This implies, we can always choose one switch, that we will never touch (we can flip all remaining 2N-1 switches instead).

For the easy data set (a 10 by 10 matrix), we can decided that we will not touch the switch for the first column and then we will try out all 2^9 possibilities for remaining 9 column switches. For each column setting, the setting of row switches is determined by minimality condition, e.g. we flip swiches in all such rows, that have more bulbs on than off.

The difficult data set.

This matrix (50 by 50 matrix) was generated from a smaller (10 by 10) matrix by making a 5 by 5 array from each bulb. Rows and columns were randomly permutated and several switches were randomly flipped. This input could be solved directly by guessing the regular structure of the matrix, converting it to a smaller matrix and then use a program for solving small inputs. But how could we guess that? Realize, that two columns (or rows) that are in the same configuration, can be treated as a single "thick" column (or  row), since if they differred in the final configuration, you could always flip one of them to make them identical. More columns (or rows) can be also merged this way. By using this heuristics, you obtain clusters of rows and columns (5 rows or columns in each cluster).

Another approach leads to a randomized solution. It consists of many times repeated this procedure. First flip a randomly selected column. Then compute a optimal setting of row switches and the number of bulbs remaining on. If the number of bulbs switched on decreases, you accept the change with a high probability (let's say 0.8). If the number decreases, you accept the change with a small probability (0.2). If you reject the change, you flip the column back and continue to the next iteration. After sufficiently many steps it converges to optimal solution.