Robots#521

Robots (Editorial)

Firstly, note that if both and are odd, then the answer is "NO". Since we need to partition the grid into two enclosed walks, and the total amount of cells is odd, then one of the walks has to pass through an odd amount of cells. If we color all cells in black and white in a checkerboard-like pattern, any enclosed walk would have to start and end at the same color. Since after every step the color of the cell changes, we need to pass an even amount of cells for the walk to be enclosed. Obviously, the answer is also "NO" for cases where min(n, m)=1, except for the case when n=1; m=4 or n=4; m=1. The rest of the cases is possible to solve.

The first two subtasks can be solved by hand and hardcoded into the program.

The rest of the subtasks will rely on an idea that we can construct an enclosed walk in a rectangle using a zigzag-like pattern, where at least one of the side lengths is even. In order to construct a solution, we will split the whole rectangle into two smaller ones.

For the third subtask, we can partition the rectangle into a 2 \times 1 piece, and a 2 \times m-1 piece.

For the fourth subtask, we can partition the rectangle into two 2 \times m pieces.

For the fifth subtask, we can partition the rectangle into two \frac{n}{2} \times m pieces.

For the sixth subtask, we can no longer blindly make a cut across one of the sides, since if either or is odd, one of the rectangles might end up having two sides of odd length, which is impossible to solve. So we have to cut out two rectangles across one of the even sides. For easier implementation, it is possible to rotate the grid when necessary, then make a vertical cut and rotate it back: this way we do not need to worry about two separate cases of cuts.

Complexity: O(n \cdot m)