USACO OPEN07 Problem 'fliptile' Analysis
by Richard Ho
First, note that flipping the same position twice leaves the grid unchanged,
hence we should only be flipping each position either once or not at all. So if
we just go through and check all combinations of flips, and record the best
combination (fewest flips) that works, we would be going through 2^(MN)
different grids, since each of the MxN positions can either have a flip or not.
While this solution is accurate, (that is, it produces correct answers given
enough time to run), it is also too slow, since for 15 by 15 grids, we would
have to consider 2^255 combinations, which is approximately 5.7896 * 10^76.
Before we discard this idea, note the following: Suppose we knew the top line
of the solution. That is, we know precisely where to flip in the top row. Then
it follows that we also know where we MUST flip in the second row to eliminate
any leftover tiles in the first row, since those are the only flips left that
can remove those tiles. Inductively, we then know where we must flip for the
third row, the fourth row, and the rest of the grid. Now, if the flips we made
in the first row does not result in a solution, then when we go all the way
down to the last row, we will reach a problem (namely, uncleared tiles). So
with this idea, we just check all possible combinations of flips IN THE FIRST
ROW, and then use the elimination described above and see if we can clear the
grid. This results in only 2^M different combinations, and 2^15 = 32768 is a
much more manageable number to check. In particular, for each of the 2^M
combinations, we have to use MN operations to check if this is a solution,
giving us a runtime of O(2^M * M N). Here is a solution that employs this idea:
#include <iostream>
using namespace std;
FILE *in = fopen("fliptile.in", "r"), *out = fopen("fliptile.out", "w");
bool data[20][20],grid[20][20];
int n,m;
void flip(int x, int y) //flips grid[][] at position (x,y)
{
grid[x][y]=!grid[x][y];
if (x>0) grid[x-1][y]=!grid[x-1][y];
if (y>0) grid[x][y-1]=!grid[x][y-1];
if (x<n-1) grid[x+1][y]=!grid[x+1][y];
if (y<m-1) grid[x][y+1]=!grid[x][y+1];
}
int solution[20][20],best[20][20];
int bestflips=1000000;
void finishsolution(void)
{
int i,j;
//first copy data to grid to work with
for (i=0;i<n;i++) for (j=0;j<m;j++) grid[i][j]=data[i][j];
//flip the things in the first row
for (j=0;j<m;j++) if (solution[0][j]==1) flip(0,j);
//starting from second row down, flip the tiles we are forced to
for (i=1;i<n;i++) for (j=0;j<m;j++)
{
solution[i][j]=grid[i-1][j];
if (grid[i-1][j]) flip(i,j);
}
//now check to see if anything is left
bool allclear=true;
for (j=0;j<m;j++) if (grid[n-1][j]) {allclear=false; break;}
if (allclear)
{
//then this is a solution. check if this is better than what we have
int flips=0;
for (i=0;i<n;i++) for (j=0;j<m;j++) if (solution[i][j]) flips++;
if (flips<bestflips) //this solution is better
{
bestflips=flips;
for (i=0;i<n;i++) for (j=0;j<m;j++) best[i][j]=solution[i][j];
}
}
}
int main(void)
{
int i,j,a;
//read in data
fscanf(in,"%i %i",&n,&m);
for (i=0;i<n;i++) for (j=0;j<m;j++)
{fscanf(in,"%i",&a); data[i][j]=(a==1);}
//generate all possible top rows
for (j=0;j<m;j++) solution[0][j]=0;
while (true)
{
finishsolution();
//generate the next higher combination
solution[0][m-1]++;
for (j=m-1;j>0;j--) if (solution[0][j]>1)
{solution[0][j]-=2; solution[0][j-1]++;}
if (solution[0][0]>1) break; //we're done
}
if (bestflips==1000000) fprintf(out,"IMPOSSIBLE\n");
else
{
for (i=0;i<n;i++) for (j=0;j<m;j++)
fprintf(out,"%i%c",best[i][j],j==m-1?'\n':' ');
}
fclose(in); fclose(out); return 0;
}
We can optimize this further by using an exclusive or (xor). So instead of
manipulating a 2-dimensional array of booleans, we manipulate an array of
32-bit integers. (We really only need 15 bits.) Below is an implementation of
this, and it is effectively O(2^M * N), since binary operations on integers are
O(1). This would allow us to compute grids up to 20 x 20 within contest limits.
#include <iostream>
using namespace std;
FILE *in = fopen("fliptile.in", "r"), *out = fopen("fliptile.out", "w");
#define BIG 100000000
int data[20],n,m,sol[20],b[20],best[20],bestflips=BIG;
int flips[1050000],line[1050000],f[20][3],fs;
char buff[100];
int main(void)
{
int i,j,a,s=1,c,t;
fscanf(in,"%i %i",&n,&m);
for (i=0;i<n;i++)
{
data[i]=0;
for (j=0;j<m;j++) {fscanf(in,"%i",&a);data[i]*=2;data[i]+=a;}
}
for (j=0;j<m;j++) s*=2;
flips[0]=0; f[0][0]=1; f[0][1]=(m==1)?2:0; f[0][2]=1; fs=0;
while (fs>=0)
{
switch(f[fs][1])
{
case 0: f[fs+1][0]=f[fs][0]<<1; f[fs+1][1]=(fs+1<m-1)?0:2;
f[fs+1][2]=f[fs][2]; f[fs][1]=1; fs++;break;
case 1: f[fs+1][0]=(f[fs][0]<<1) + 1; f[fs+1][1]=(fs+1<m-1)?0:2;
f[fs+1][2]=f[fs][2]+1; f[fs][1]=2; fs++; break;
case 2: flips[f[fs][0]]=f[fs][2]; fs--; break;
}
}
t=s-1; for (i=0;i<s;i++) line[i]=i^(i>>1)^((i<<1)&t);
for (sol[0]=0;sol[0]<s;sol[0]++)
{
for (i=0;i<n;i++) b[i]=data[i];
for (i=0,a=0;i<n;i++)
{
a+=flips[sol[i]];
b[i]^=line[sol[i]];
if (i+1<n) {sol[i+1]=b[i]; b[i+1]^=sol[i];}
}
if (b[n-1]==0 && a<bestflips)
{
bestflips=a;
for (i=0;i<n;i++) best[i]=sol[i];
}
}
if (bestflips==BIG) {fprintf(out,"IMPOSSIBLE\n"); return 0;}
for (j=0;j<m;j++) buff[2*j+1]=(j==m-1)?'\0':' ';
for (i=0;i<n;i++)
{
a=best[i];
for (j=m-1;j>=0;j--) {buff[2*j]=(a%2==0)?'0':'1'; a/=2;}
fprintf(out,"%s\n",buff);
}
fclose(in); fclose(out); return 0;
}
For those who are more math-oriented, if we diverge a bit from the problem, it
is possible to find *a* solution in polynomial time, although this solution
would not necessarily be the most optimal. If you are interested in how this is
done, please refer to http://mathworld.wolfram.com/LightsOutPuzzle.html