← All solutions

Shortest judge solution: 1637 bytes. Shortest team solution (during contest): 1440 bytes.

Python solutions by the judges: none

The judges had this pegged as a medium difficulty problem but the teams apparently felt otherwise. There are a few small observations to make, in order to understand how to solve the problem.

The first thing to realize is that when applying a step of the process, the bounding box of the pattern always grows by at least one step in every dimension, even if there is an error. Equivalently: without errors, the resulting bounding box after an evolution step will have at least 2 filled cells on every side. In other words, when going backwards, the bounding box will shrink by at least one step in each dimension for every step. This means that the total number of iterations to go backwards can be at most min((n + 1)/2, (m + 1)/2).

Suppose for a moment that no errors happen. Then we can simply reconstruct the previous pattern X from the current pattern Y row by row – if we’re reconstructing cell (r, c), and have already reconstructed all rows r⁰ < r, and all cells (r⁰, c⁰) with r⁰ = r and c⁰ < c, then we can compute the previous value X_r,c by Y_r−1,c−1 ⊕ X_r−2,c−2 ⊕ X_r−2,c−1 ⊕ X_r−2,c ⊕ X_r−1,c−2 ⊕ X_r−1,c−1 ⊕ X_r−1,c ⊕ X_r,c−2 ⊕ X_r,c−1 (where ⊕ is XOR a.k.a. addition mod 2). Proceeding in this way we can reconstruct the previous step.

OK, that’s easy, but what if there are errors, how do we even detect that? Suppose that cell (r, c) has an error. By the observation above, this will cause the reconstruction of cell X_r+1,c+1 to get the wrong value. This will in turn cause X_r+1,c+2 to get the wrong value. However, then X_r+1,c+3 will actually get the correct value, because the two errors from X_r+1,c+1 and X_r+1,c+2 cancel out. Then similarly X_r+1,c+4 and X_r+1,c+5 will get the wrong value, and X_r+1,c+6 will get the right value, and it will continue cycling like that with two incorrect cells followed by one correct cell. That means that when we get to the end of the row, we can verify that the first two cells that should be outside the bounding box (by the observation above) become empty. If an error happened in row r, at least one of these two cells will get an error and become non-empty. When this happens, we can run the reconstruction again, but column by column instead of row by row, which allows to detect that an error happened in row c. We have then found the error, can undo it, and then run the reconstruction step again to get to the previous pattern.

The process ends when the pattern is either a single filled cell, or if the reconstruction process still finds errors after the first error is fixed. Going back one iteration using the above process takes O(n · m) time, so by the observation above on the maximum number of iterations, this results in an O((n + m)³) time algorithm.

Note that there are actually no choices to make in how to do the reconstruction, meaning that the answer is in fact uniquely determined (though figuring this out was part of solving the problem).