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