This problem is to be found here: http://ipsc.ksp.sk/contests/ipsc1999/re ... lems/f.php
The panel is a square consisting of N rows of bulbs with N bulbs in each row. However, it has only 2N switches - one for each row and one for each column. The switch for a given row (or a column) turns off all the bulbs in a given row (or a column) which are on and turns on all the bulbs which are off. It might not be possible to turn off all the bulbs of the panel. Your task is to determine a configuration of the panel with the least number of shining bulbs that can be achieved using the switches.
Input specification
The input describes the initial configuration of the advertising panel. The first line consists of a single number N. Each of the next N lines describes one row of the panel starting from the top. It contains N numbers separated by spaces - each number standing for one bulb, 1 if the bulb is on, 0 if the bulb is off, starting from the left.
Output specification
The first line of the output contains one integer M, giving the minimum number of shining bulbs. The next N lines describe one of possible minimum final configurations in the same format as was the initial configuration in the input described. To prevent the problems with the mailer you may split long lines into several shorter ones.
Example
Input file:
4
1 0 1 1
1 0 1 0
1 1 1 0
0 1 0 0
Output file:
3
0 0 0 0
0 0 0 1
0 1 0 1
0 0 0 0
I already know the BF solution and the Monte-Carlo one. Does anyone know anything faster than bf, maybe some polynomial algorithm or anything better? And it should be reliable of course.
Panel
Moderator: Board moderators
The problem is NP-complete.
It isn't hard to see that you can reduce the problem to 1 dimension - pick the rows and the columns follow.
Here are 2 observations:
1. In the contest, I solved this by using brute force when n < 25 and a heuristic when n >= 25.
2. This is a "submit the result" contest so you are allowed to look at the input. If you plotted the input, you'd see that the hard case consisted of a tiling of smaller cases that were brute-forceable.
It isn't hard to see that you can reduce the problem to 1 dimension - pick the rows and the columns follow.
Here are 2 observations:
1. In the contest, I solved this by using brute force when n < 25 and a heuristic when n >= 25.
2. This is a "submit the result" contest so you are allowed to look at the input. If you plotted the input, you'd see that the hard case consisted of a tiling of smaller cases that were brute-forceable.
hi.
i assume BF comes from brute force. also i assume by BF in this case u mean the one presented on the page for the easy test-case.
what is the monte-carlo solution?
what euristic method have u used, the one they present?
please clarify theese things to me.
here's some math i did on this. is it accurate?
small tests:
u have 2^(n-1) combinations of column switches.
then for n rows compute number of 1's, see if switch is needed =>n^2 ops (matrix acceses).
total is about 2^(n-1)*n^2
(pretty large for n=25 isn't it???)
large tests:
i aprove the 1st method, of merging since it is 100% (though in unpredictable time). after the merge u have an MxP matrix with M<N and P<N. the merge is relatively time inexpensive:
(my idea)
for (i=0;i<N;i++){
do sum;
for (j=0;j<i;j++)
if (sum==sum[j] || sum==(n-sum[j])) //second uses switch
add j to cluster of i;
}
this should reach about n^2 i guess.
then apply short test algo => 2^(M-1)*P^2*N^2
ofcourse, if P<M, the algo should be applied for combs of P-1 rows, then the M columns, to minimize the exponential.
two problems here:
1. N rows can have 2^(n-1) distinct (even if flipped) combinations of lit bulbs, that will not match so will not be clustered. Then problem remains unsolved
2. some clusters may have more rows/cols then others so i guess small test algo should b modified to accept an array of weights for each row/col, right?
the randomization solution i don't like because it may yield an aprox result, but still wrong so.. the problem is again unsolved.
maybe a greedy&then randomization could do...
BTW can greedy enter an endless loop here? i'll try to code greedy when i have some time seee what gives.
Srry for such a long post, thx for any replies. Very interestin problem...
i assume BF comes from brute force. also i assume by BF in this case u mean the one presented on the page for the easy test-case.
what is the monte-carlo solution?
what euristic method have u used, the one they present?
please clarify theese things to me.
here's some math i did on this. is it accurate?
small tests:
u have 2^(n-1) combinations of column switches.
then for n rows compute number of 1's, see if switch is needed =>n^2 ops (matrix acceses).
total is about 2^(n-1)*n^2
(pretty large for n=25 isn't it???)
large tests:
i aprove the 1st method, of merging since it is 100% (though in unpredictable time). after the merge u have an MxP matrix with M<N and P<N. the merge is relatively time inexpensive:
(my idea)
for (i=0;i<N;i++){
do sum;
for (j=0;j<i;j++)
if (sum==sum[j] || sum==(n-sum[j])) //second uses switch
add j to cluster of i;
}
this should reach about n^2 i guess.
then apply short test algo => 2^(M-1)*P^2*N^2
ofcourse, if P<M, the algo should be applied for combs of P-1 rows, then the M columns, to minimize the exponential.
two problems here:
1. N rows can have 2^(n-1) distinct (even if flipped) combinations of lit bulbs, that will not match so will not be clustered. Then problem remains unsolved
2. some clusters may have more rows/cols then others so i guess small test algo should b modified to accept an array of weights for each row/col, right?
the randomization solution i don't like because it may yield an aprox result, but still wrong so.. the problem is again unsolved.
maybe a greedy&then randomization could do...
BTW can greedy enter an endless loop here? i'll try to code greedy when i have some time seee what gives.
Srry for such a long post, thx for any replies. Very interestin problem...
Understanding a problem in a natural way will lead to a natural solution