First, let's show that it is impossible to beat the game if the number of heads is initially even. For the sake of contradiction, assume some sequence of moves that removes all the coins exists. Then, let's split each coin removal into two components and analyze what happens to the parity of the number of heads independently:

1. The coin that was removed disappearing from the grid.
2. The adjacent coins being flipped as a result of the removal.

For the first component, note that a heads disappearing from the grid obviously changes the parity of the number of heads. Since this happens ~N \times M~ times and ~N \times M~ is odd, the overall parity of the number of heads will change by the end of the removal process.

For the second component, we can visualize each cell of the grid as a vertex of a graph, with edges connecting vertices that represent adjacent cells in the grid. Then, the number of times a coin is flipped after removing all ~N \times M~ coins is exactly the number of edges in this graph. After all, exactly one coin out of each neighbouring pair will be flipped. It is not hard to see that this graph has an even number of edges, so the overall parity of the number of heads remains constant from component 2.

Combining the two components, we have just shown that the parity of the number of heads must change when we remove all of the coins. However, this tells us that there should be an odd number of heads when the sequence of removals is complete, a clear contradiction of the fact that there are ~0~ coins left! Thus, we may conclude that it is impossible to beat the game if the number of heads is initially even.

Now that we've shown that it is necessary for the initial number of heads to be odd if the game is solvable, we will also demonstrate its sufficiency by way of construction for the two subtasks below.

Subtask 1

It is easy to see via induction that simply removing the leftmost heads at any point removes all ~M~ coins. This can be implemented with a simple loop from left to right over the grid.

Time Complexity: ~\mathcal{O}(NM)~

Subtask 2

The solution to the previous subtask gives us a means of removing any row of the grid provided that there are an odd number of coins in that row. Now, the key observation is to assign a single representative coin to each row of the grid, heads if the number of heads in that row is odd or tails otherwise. Then, since each row contains an odd number of coins, removing any row will change the parity of the number of heads in the rows above and below it, essentially flipping their representative coins! This reduces the problem back down to a vertical 1-D strip of ~N~ coins, which we already have a nice solution for. Note that the number of representative coins that are heads must be odd if the total number of heads is odd, so this method is always sufficient to solve the problem for any grid of coins with an odd number of heads.

Time Complexity: ~\mathcal{O}(NM)~

Remarks:

• Note that the solution given in the second subtask can be easily generalized to work for any ~k~-dimensional lattice of coins.
• The solution provided will also work for any 2-D grid where at least one of the dimensions is odd. However, it turns out that grids with both dimensions even are much harder to solve! Specifically, it is hard to even determine whether a given grid is solvable or not. The same proof of impossibility on even dimensions shows that it is necessary for the number of heads to be even, but sufficiency is nowhere near as simple. For example, it can be shown that the following grids are not solvable even though the number of heads is even:

2 4
TTTT
THHT

4 4
TTTT
HTTH
HTTH
TTTT

4 4
THHT
HTTH
HTTH
THHT

• In general, grids where the corner cells and the inner ~(N-2) \times (M-2)~ grid are all T and the edges are paired into equal adjacent coins compose one such family of nontrivial cases. Credit goes to zhouzixiang2004 for discovering these.