## 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 2**N**-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.