CodeChef submission 53306 (C++ 4.0.0-8) plaintext list. Status: TLE, problem EX, contest JULY09. By gmark (Mark Greve), 2009-07-10 15:18:59.
// Lights Off, Revisited!
// Source: CodeChef July 2009 Challenge
// CodeChef ID: EX
// Date: 06-07-2009
// Author: Mark Greve
// Keywords: DP
// Status: AC
// Difficulty: hard
// Complexity:
// Comments:
// This solution uses only E and W moves and then uses DP to compute the best
// solution row-by-row (trying the best combination). Also, we attempt to
// transpose the matrix and try again. This solution also uses a more advanced DP approach,
// which is unfortunately a bit slower.
//
// This is the best solution so far.
// Now with timing code...
//
// Three criteria:
// 1. Minimum penalty
// 2. Minimum number of moves
// 3. Rows differing as much as possible
 
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;
 
// TIMING CODE
#include <sys/time.h>
#include <sys/resource.h>
#include <stdint.h>
#include <time.h>
 
typedef uint_fast64_t test_realtime_t;
 
inline void get_test_realtime(test_realtime_t& a) {
	struct timeval tv;
	gettimeofday(&tv, NULL);
	a = tv.tv_sec;
	a *= 1000*1000;
	a += tv.tv_usec;
}
 
inline uint_fast64_t testRealtimeDiff(const test_realtime_t a, const test_realtime_t b) {
	return b - a;
}
// END TIMING CODE
 
#define MP make_pair
typedef pair<int,int> pii;
typedef vector<pair<pii,char> > vsol;
 
const int MAX=1005;
int B[MAX][MAX];
int C[MAX][MAX];
int n;
const int INF=1<<29;
 
// UTILITY FUNCTIONS
void show_board() {
	printf("N: %d\n", n);
	for (int i=0;i<n;++i) {
		for (int j=0;j<n;++j) printf("%d", B[i][j]);
		printf("\n");
	}
}
char transpose_dir(char c) {
	if (c=='E') return 'S';
	if (c=='W') return 'N';
	if (c=='S') return 'E';
	if (c=='N') return 'W';
}
 
void perform(int y, int x, char d) {
	if (d=='N') { while (y>=0) B[y][x] = !B[y][x], --y; }
	if (d=='S') { while (y<n)  B[y][x] = !B[y][x], ++y; }
	if (d=='E') { while (x<n)  B[y][x] = !B[y][x], ++x; }
	if (d=='W') { while (x>=0) B[y][x] = !B[y][x], --x; }
}
void transpose() {
	for (int i=0;i<n;++i)
		for (int j=0;j<i;++j)
			swap(B[i][j],B[j][i]);
}
// Count the number of ones on the board.
int countones() {
	int cnt = 0;
	for (int i=0;i<n;++i)
		for (int j=0;j<n;++j)
			cnt += B[i][j];
	return cnt;
}
void copy_back() {
	for (int i=0;i<n;++i)
		for (int j=0;j<n;++j)
			B[i][j] = C[i][j];
}
void show_sol(const vsol& moves) {
	printf("%d\n", moves.size());
	for (int i=0;i<moves.size();++i)
		printf("%d %d %c\n", moves[i].first.first, moves[i].first.second, moves[i].second);
}
// Copy only the unique moves over
vsol fixmoves(vsol moves) {
	sort(moves.begin(),moves.end());
	vsol moves2;
	int cnt = 0;
	for (int i=0;i<moves.size();++i) {
		if (i==0 || moves[i] == moves[i-1]) ++cnt;
		else {
			if (cnt%2==1) moves2.push_back(moves[i-1]);
			cnt = 1;
		}
	}
	if (cnt%2==1)  moves2.push_back(moves.back());
	return moves2;
}
// NESW
const int dy[]={-1,0,1,0};
const int dx[]={ 0,1,0,-1};
char dir2c(int x) {
	switch(x) {
		case 0: return 'N';
		case 1: return 'E';
		case 2: return 'S';
		case 3: return 'W';
	}
}
// END UTILITY FUNCTIONS
 
 
// SMALL CASE SOLVER
const int MAXD=3;
int dpsmall[MAXD][MAXD][1<<(MAXD*MAXD)];
int choicesmall[MAXD][MAXD][1<<(MAXD*MAXD)];
int newns[MAXD][MAXD][1<<(MAXD*MAXD)];
 
template<class T> inline int BITCNT(T x){int r=0;while(x){r++;x&=x-1;}return r;}
 
int go_small(int y, int x, int s) {
	if (y==MAXD) return BITCNT(s);
	if (x==MAXD) return go_small(y+1,0,s);
	int& ref = dpsmall[y][x][s];
	if (ref!=-1) return ref;
	int& ch = choicesmall[y][x][s];
	int& news = newns[y][x][s];
	ch = 0;
	news = s;
	ref = go_small(y,x+1,s);
	for (int k=0;k<4;++k) {
		int ns = s;
		int ny = y;
		int nx = x;
		while (0 <= nx && nx < MAXD && 0 <= ny && ny < MAXD) {
			ns ^= (1<<(ny*MAXD + nx));
			ny += dy[k];
			nx += dx[k];
		}
		int next = 2 + go_small(y,x+1,ns);
		if (next<ref) {
			ch = k+1;
			ref = next;
			news = ns;
		}
	}
	return ref;
}
 
int get_moves_small(int y, int x, int oy, int ox, int s, vsol& moves, bool transposed) {
	if (y==MAXD) return s;
	if (x==MAXD) return get_moves_small(y+1,0,oy,ox,s,moves,transposed);
	int ch = choicesmall[y][x][s];
	int ns = newns[y][x][s];
 
	if (ch==0) return get_moves_small(y,x+1,oy,ox,ns,moves,transposed);
	--ch;
	
	if (!transposed) moves.push_back(MP(MP(oy + y,ox + x), dir2c(ch)));
	else             moves.push_back(MP(MP(ox + x, oy + y),transpose_dir(dir2c(ch))));
	
	// Might be invalid
	if (ch==0)      moves.push_back(MP(MP(oy - 1   , ox+x   ), dir2c(ch))); // N
	else if (ch==1) moves.push_back(MP(MP(oy+y     , ox+MAXD), dir2c(ch))); // E
	else if (ch==2) moves.push_back(MP(MP(oy + MAXD, ox+x   ), dir2c(ch))); // S
	else if (ch==3) moves.push_back(MP(MP(oy+y     , ox-1   ), dir2c(ch))); // W
	if (transposed) {
		swap(moves.back().first.first, moves.back().first.second);
		moves.back().second = transpose_dir(moves.back().second);
	}
 
	// So prune it
	if (
			moves.back().first.first  >= n || moves.back().first.first  < 0 || 
			moves.back().first.second >= n || moves.back().first.second < 0
		 )
		moves.pop_back();
 
 
	return get_moves_small(y,x+1,oy,ox, ns, moves, transposed);
}
 
// Run over then entire board and optimize all MAXDxMAXD squares
void do_small_case_solve(vsol& moves, bool transposed) {
	for (int y=0;y+MAXD-1<n;++y) {
		for (int x=0;x+MAXD-1<n;++x) {
 
			int s = 0;
			for (int _dy=0;_dy<MAXD;++_dy) {
				for (int _dx=0;_dx<MAXD;++_dx) {
					if (B[y+_dy][x+_dx])
						s |= (1<<(MAXD*(_dy) + _dx));
				}
			}
 
			go_small(0,0,s);
			int ns = get_moves_small(0,0,y,x,s,moves,transposed);
			for (int _dy=0;_dy<MAXD;++_dy)
				for (int _dx=0;_dx<MAXD;++_dx)
					B[y+_dy][x+_dx] = bool(ns&(1<<( MAXD*(_dy) + _dx)));
		}
	}
}
 
// END SMALL CASE SOLVER
 
vsol tmpmoves; // Stores the temporary moves for any get_moves method
 
// DP to compute the minimum possible penalty for a row (using east moves)
int dp_east[MAX][2];
int choice_east[MAX][2];
int min_cost_row_east(int r, int at, int flip) {
	if (at>=n) return 0;
	int& ref = dp_east[at][flip];
	if (ref!=-1) return ref;
	int state = (B[r][at] ^ flip);
	int& ch = choice_east[at][flip];
	ch = 0;
 
	// Try doing nothing.
	ref = (state<<20) + min_cost_row_east(r, at+1, flip) + (r>0 ? B[r-1][at]!=state : 0);
 
	// Try flipping east here.
	int other = (1<<1) + ((1 + (!state))<<20) + min_cost_row_east(r,at+1,!flip) + (r>0 ? B[r-1][at]!=(!state) : 0);
 
	if (other<=ref) { // Prefer the flip or not ? (<= vs <)
		ref = other;
		ch = 1;
	}
	return ref;
}
 
void get_moves_east(int r, int at=0, bool flip=0, bool transposed=0) {
	if (at>=n) return;
	if (choice_east[at][flip]==0) return get_moves_east(r, at+1,flip,transposed);
	if (!transposed) tmpmoves.push_back(MP(MP(r,at),'E'));
	else             tmpmoves.push_back(MP(MP(at,r),'S'));
	get_moves_east(r, at+1, !flip, transposed);
}
 
int dp_west[MAX][2];
int choice_west[MAX][2];
 
 
// DP to compute the minimum possible penalty for a row (using west moves)
int min_cost_row_west(int r, int at, int flip) {
	if (at<0) return 0;
	int& ref = dp_west[at][flip];
	if (ref!=-1) return ref;
	int state = (B[r][at] ^ flip);
	int& ch = choice_west[at][flip];
	ch = 0;
	// Try doing nothing.
	ref = (state<<20) + min_cost_row_west(r, at-1, flip) + (r>0 ? B[r-1][at]!=state : 0);
 
	// Try flipping west here.
	int other = (1<<1) + ((1 + (!state))<<20) + min_cost_row_west(r,at-1,!flip) + (r>0 ? B[r-1][at]!=(!state) : 0);
 
	if (other<=ref) { // Prefer the flip or not ? (<= vs <)
		ref = other;
		ch = 1;
	}
	return ref;
}
 
void get_moves_west(int r, int at=n-1, bool flip=0, bool transposed=0) {
	if (at<0) return;
	if (choice_west[at][flip]==0) return get_moves_west(r, at-1,flip, transposed);
	if (!transposed) tmpmoves.push_back(MP(MP(r,at),'W'));
	else             tmpmoves.push_back(MP(MP(at,r),'N'));
	get_moves_west(r, at-1, !flip, transposed);
}
 
// Solve a row in O(n^2) using WEST as a prefix and EAST as a suffix
// Insert the moves into moves and simulate the moves
void solve_row_naive(int y, vsol& moves, bool transposed, bool simulate=1) {
	// Clear the DP tables
	for (int x=0;x<n;++x) dp_east[x][0]=dp_east[x][1]=-1;
	for (int x=0;x<n;++x) dp_west[x][0]=dp_west[x][1]=-1;
 
	// Find the best combination
	int minv = -1, idx = -1;
	for (int pre=-1;pre<n;++pre) {
		int cost = min_cost_row_west(y,pre,0) + min_cost_row_east(y,pre+1,0);
		if (minv==-1 || (cost<minv)) {
			minv = cost;
			idx = pre;
		}
	}
	if (simulate) {
		tmpmoves.clear();
		get_moves_west(y,idx,0,transposed);
 
		// Simulate the WEST moves
		bool flip = 0;
		int at = idx;
		for (int i=0;i<tmpmoves.size();++i) {
			int x = (!transposed ? tmpmoves[i].first.second : tmpmoves[i].first.first);
			while (at>x) B[y][at] ^= flip, --at;
			flip = !flip;
		}
		while (at>=0) B[y][at] ^= flip, --at;
 
		int bef = tmpmoves.size();
		get_moves_east(y,idx+1,0,transposed);
 
		// Simulate the EAST moves
		at = idx+1;
		flip = 0;
		for (int i=bef;i<tmpmoves.size();++i) {
			int x = (!transposed ? tmpmoves[i].first.second : tmpmoves[i].first.first);
			while (at<x) B[y][at] ^= flip, ++at;
			flip = !flip;
		}
		while (at<n) B[y][at] ^= flip, ++at;
 
		moves.insert(moves.end(), tmpmoves.begin(),tmpmoves.end());
	}
}
 
test_realtime_t START_TIME; // global start time
 
// Solve, transpose and call recursively to solve again
// using the more naive DP approach (but faster, i.e. O(n^2))
void naivesolver(int bound, vsol& moves, bool transposed, int TIMEBOUND) {
	int runs = 0;
	while (runs<=bound) {
 
		for (int y=0;y<n;++y) {
			if (y%100==0) {
				test_realtime_t a;
				get_test_realtime(a);
				if (testRealtimeDiff(START_TIME,a)>=TIMEBOUND) return;
			}
			solve_row_naive(y,moves,transposed);
		}
 
		transpose();
		transposed = !transposed;
		++runs;
	}
}
 
int solve(vsol& moves) {
 
	// Transposed solution
	vsol sol0;
	//naivesolver(INF,sol0,0,4300000);
	//sol0 = fixmoves(sol0);
	int cost0 = moves.size() + countones() + sol0.size(); // Compute the real cost.
 
	// Not transposed
	copy_back();
	transpose();
	vsol sol1;
	naivesolver(INF,sol1,1,4500000);
	sol1  = fixmoves(sol1);
	int cost1 = moves.size() + countones() + sol1.size();
 
	if (cost0<cost1) moves.insert(moves.end(),sol0.begin(),sol0.end());
	else             moves.insert(moves.end(),sol1.begin(),sol1.end());
	return min(cost0,cost1);
}
 
// FAST IO
char *start;
const int MAXBUF=30000000;
char buf[MAXBUF];
void skip() {
	while (*start != 0  && !('0' <= *start && *start <= '9')) start++;
}
void GETNUM(int& n){
	skip();
	n=0;
	while ('0' <= *start && *start <= '9') {
		n = n*10 + *start-'0', ++start;
	}
}
 
// END FAST IO
 
void take_input() { // Take input using fast I/O
	int sz=fread(buf, sizeof(char), MAXBUF, stdin);
	buf[sz]=0;
	start=buf;
	GETNUM(n);
 
	for (int i=0;i<n;++i) {
		for (int j=0;j<n;++j) {
			GETNUM(B[i][j]);
			C[i][j] = B[i][j];
		}
	}
}
 
int main() {
	get_test_realtime(START_TIME);
	//memset(dpsmall,-1,sizeof dpsmall);
	take_input();
	vsol sol0;
	int cost0 = solve(sol0);
	show_sol(sol0);
}