(Analysis by Brian Dean)

Let's first look at this puzzle without the one exceptional cow, to try and gain an understanding of when it is solvable and when it isn't. It helps to think of a minimal example that is not solvable, which turns out to be:


Here, we are switching to 0s and 1s instead of Ls and Rs for convenience. If you think about this example for a few moments, you notice that no matter how many times you toggle rows and columns, there will always be 3 of one bit and 1 of the other --- it is never possible to make all four bits agree.

In fact, this ends up being the only bad structure that can prevent us from solving the puzzle. If we have any four bits that are corners of a rectangle where three of the four agree (let's call this a "bad rectangle"), then the puzzle is not solvable, and this is for the same reason as above, since exactly three of the four bits will always agree no matter what rows and columns we toggle. This condition, which persists throughout the toggling of rows and columns, is called an "invariant", and many times when you see unsolvable puzzles like this, it helps to try and find some sort of invariant that prevents solution of the puzzle.

Suppose now that there aren't any bad rectangles. Let's try to make the entire grid into 0s as follows: for any 1 in the top row, flip its entire column. Then for any 1 in the left row, flip its entire row. This transforms the top row and left column into all 0s. If all the other entries are 0s, we are done. Otherwise, if there is a 1 somewhere, this in combination with the top row and left column forms a bad rectangle, which we had assumed could not exist. Hence, the puzzle is actually solvable if and only if there is no bad rectangle.

The insight above is now enough to add back the one exceptional cow. Let's proceed as before to set the top row and left column to all zeros. If the remaining elements are all 1s, then the top-left element was the exceptional cow. If any row or column is filled with 1s (except the first element, which we have set to zero), then its first element is the exceptional cow. Otherwise, there should be a single 1 somewhere in the grid, which indicates the position of the exceptional cow.

My code in C++ is below.

#include <iostream>
#include <fstream>
using namespace std;
int N;
char grid[1000][1000];
int num(int i1, int j1, int i2, int j2, int b)
  int total = 0;
  for (int i=i1; i<=i2; i++)
    for (int j=j1; j<=j2; j++)
      if (grid[i][j] == b) total++;
  return total;
int main(void)
  ifstream fin ("leftout.in");
  string s;
  fin >> N;
  for (int i=0; i<N; i++) {
    fin >> s;
    for (int j=0; j<N; j++) grid[i][j] = s[j]=='L';
  // Flip columns and rows so top row and left column all zero
  for (int i=1; i<N; i++) {
    grid[i][0] = grid[i][0] ^ grid[0][0];
    for (int j=1; j<N; j++) grid[i][j] = grid[i][j] ^ grid[0][j] ^ grid[i][0];
  ofstream fout ("leftout.out");
  if (num (1,1,N-1,N-1,0) == 0) { fout << "1 1\n"; return 0; }
  if (num (1,1,N-1,N-1,1) == N-1) {
    for (int j=1; j<N; j++) if (num(1,j,N-1,j,1)==N-1) { fout << "1 " << j+1 << "\n"; return 0; }
    for (int i=1; i<N; i++) if (num(i,1,i,N-1,1)==N-1) { fout << i+1 << " 1\n"; return 0; } 
    fout << "-1\n"; return 0;
  if (num(1,1,N-1,N-1,1)!=1) { fout << "-1\n"; return 0; } 
  for (int i=1; i<N; i++)
    for (int j=1; j<N; j++)
      if (grid[i][j]==1) { fout << i+1 << " " << j+1 << "\n"; }
  return 0;