Sharing Pepero

Subtask 1 Let $K$ be the number of empty cells. Enumerate all $2^K$ direction assignments. Mark rows containing a horizontal box and columns containing a vertical box, then check every student. This takes $O(2^K NM)$ time.

Full solution If every row has an empty cell, direct every box horizontally. Every student receives Pepero from a box in their row. Likewise, if every column has an empty cell, directing every box vertically works.

If neither condition holds, there is a row with no empty cells and a column with no empty cells. The student at their intersection cannot receive Pepero from either direction. Thus the assignment is impossible. This proves both the decision rule and the construction.

The time complexity, including input and output, is $O(NM)$. Storing the grid uses $O(NM)$ space.

Solution written by GPT6.1