CareerCup

E.g.
0, 1, 1,
0, 1, 1,
0, 0, 0,
--- Flip(0, 1)
1, 0, 0,
0, 0, 1,
0, 1, 0,
--- Flip(1, 1)
1, 1, 0,
1, 1, 0,
0, 0, 0,
--- Flip(2, 1)
1, 0, 0,
1, 0, 0,
1, 1, 1,
--- Flip(2, 0)
0, 0, 0,
0, 0, 0,
0, 0, 0,

Brute force:

#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;

void Flip(vector<vector<bool>> &m, int r, int c)
{
	for (int i = 0; i < m.size(); ++i) {
		m[i][c] = !m[i][c];
	}
	for (int i = 0; i < m[r].size(); ++i) {
		m[r][i] = !m[r][i];
	}
	m[r][c] = !m[r][c];
}

bool Zeroable(vector<vector<bool>> &m, unordered_set<string> &seen)
{
	if (!m.empty() &&
		!m[0].empty())
	{
		int zeros = 0;
		string key;
		for (auto &r : m) {
			for (bool val : r) {
				if (val == false) {
					++zeros;
				}
				key += val;
			}
		}
		if (zeros == m.size() * m[0].size()) {
			return true;
		}
		if (seen.find(key) != seen.end()) {
			return false;
		}
		seen.insert(key);
		for (int r = 0; r < m.size(); ++r) {
			for (int c = 0; c < m[r].size(); ++c) {
				Flip(m, r, c);
				if (Zeroable(m, seen)) {
					return true;
				}
				Flip(m, r, c);
			}
		}
	}
	return false;
}

void Print(vector<vector<bool>> const &m)
{
	for (auto &r : m) {
		for (bool val : r) {
			cout << val << ", ";
		}
		cout << "\n";
	}
	cout << "---\n";
}

int main()
{
	srand(time(NULL));

	int n = 3;
	int m = 4;

	while (true) {
		vector<vector<bool>> matrix(m, vector<bool>(n));
		for (int r = 0; r < matrix.size(); ++r) {
			for (int c = 0; c < matrix[r].size(); ++c) {
				matrix[r][c] = rand() % 2;
			}
		}
		auto orig = matrix;
		unordered_set<string> seen;
		if (Zeroable(matrix, seen)) {
			Print(orig);
		}
	}
}

For square matrix n.

For n,m matrix, where n<m, then n+1.

Draw a matrix of 0s, and iterate it on its diagonal- regardless of the matrix shape, and you will figure it out why.

does the field I click flip as well? The problem statement sais it's flipped twice = it's not flipped.

the only way I can think of is to start from a matrix of 0s
and click several random points
but I dont see clear patterns.

If x+y-1 is odd you can make any pattern with row/column flips.
Else
If the exor of all cells is 0 then this is a valid pattern
However if it is 1 then you cannot make that pattern
Label all cells in the grid with capital letters
ABC
DEF

Let the lower case letter be true if it was the center of a flip
a= true
111
100

Write the equation for each cell
A = a exor b exor c exor d
B = a exor b exor c exor e
C…

Exor all capital letters
Simplify
z exor z -> 0
0 exor z -> z
…
When you flip a row / column you change x+y-1 cells
If(x+y-1) is even then the exor of all bits will = 0
If(x+y-1) is odd then exor of A….. = exor a…. so that does not matter

If someone can write a better explanation please do. It took me a long time to figure this out and I want to move on. It seems like a induction proof would be good for this.

Generally not possible.
Only possible if size of matrix is either 1x n or n x 1 or 1 x 1,
And all values of matrix are same.