A. Crystal Crosswind

Key Observations

• Fix one wind and one cell $p$. Let $\mathrm{prev}(p)$ be the cell at $p-(w_x, w_y)$.

• If $p$ is listed as a boundary for that wind, then we know two facts exactly: \[ p = 1,\qquad \mathrm{prev}(p) = 0 \] whenever $\mathrm{prev}(p)$ lies inside the grid.

• If $p$ is not listed as a boundary, then the forbidden situation is ``$p$ contains a molecule and $\mathrm{prev}(p)$ does not''. Therefore we get the implication \[ p = 1 \Longrightarrow \mathrm{prev}(p) = 1. \]

• This is a Horn-style system: some cells are forced to be present, some are forced to be absent, and every remaining rule is a one-way implication between cells.

• In such a system:

  • the minimal solution is obtained by starting from all forced-present cells and repeatedly applying implications;

  • the maximal solution is obtained by starting from all forced-absent cells and repeatedly applying the reverse rule ``if the predecessor is absent, then the current cell must also be absent''.

  Algorithm

  1. Store, for every wind, a boolean table telling whether each cell is listed as a boundary.

  2. Build the set of forced-present cells: every observed boundary cell must contain a molecule.

  3. Build the set of forced-absent cells from two sources:

     • the predecessor of every boundary cell;

     • any cell whose predecessor lies outside the grid and which is not listed as a boundary, because such a cell cannot contain a molecule.

     • To obtain the minimal structure, run a BFS/queue over forced-present cells. When a cell $p$ is known to be present and $p$ is not a boundary for some wind, mark $\mathrm{prev}(p)$ present as well.

     • To obtain the maximal structure, run a BFS/queue over forced-absent cells. When a cell $q$ is known to be absent and another cell $p=q+(w_x,w_y)$ is inside the grid and is not a boundary for that wind, then $p$ must also be absent.

     • Output the cells marked present in each construction. enumerate

       Correctness Proof

       We prove that the algorithm outputs exactly the minimal and maximal valid crystal structures.

       Lemma 1.

       Every cell marked present by the minimal-construction BFS must be present in every valid solution.

       Proof.

       Initially, every queue element is an observed boundary cell, so it is forced to be present by definition.

       Whenever the BFS processes a present cell $p$ and, for some wind, $p$ is not a boundary, the observation rules imply $p = 1 \Rightarrow \mathrm{prev}(p) = 1$. Therefore the predecessor is also present in every valid solution. By induction over the BFS order, every marked cell is mandatory. □

       Lemma 2.

       The grid produced by the minimal-construction BFS is itself valid.

       Proof.

       All observed boundary cells are marked present, so the positive part of every boundary constraint is satisfied.

       All predecessors of observed boundary cells were put into the forced-absent set, and the input is guaranteed consistent, so none of them is marked present by the BFS. Thus the negative part of every boundary constraint is also satisfied.

       Finally, whenever a marked-present cell $p$ is not a boundary for some wind, the BFS explicitly enforces that its predecessor is also marked present. Hence every non-boundary implication is satisfied. Therefore the produced grid is valid. □

       Lemma 3.

       Every cell marked absent by the maximal-construction BFS must be absent in every valid solution.

       Proof.

       Initially, every queue element is forced absent either because it is the predecessor of an observed boundary or because it would otherwise create an unobserved boundary at the edge of the grid.

       Whenever the BFS processes an absent cell $q$, consider a wind and the cell $p=q+(w_x,w_y)$. If $p$ is not a boundary for that wind, then the constraint is $p = 1 \Rightarrow q = 1$. Since $q$ is absent, $p$ cannot be present, so $p$ is also forced absent. Induction on the BFS order proves the claim. □

       Lemma 4.

       Setting every cell not marked absent by the maximal-construction BFS to present yields a valid solution.

       Proof.

       All forced-absent cells are kept absent, so every boundary predecessor is absent as required. Also, boundary cells themselves are never marked absent in a consistent instance, so they remain present.

       Now consider any non-boundary implication $p = 1 \Rightarrow \mathrm{prev}(p) = 1$. If $p$ were present while $\mathrm{prev}(p)$ were absent, then during the maximal-construction BFS the absence of $\mathrm{prev}(p)$ would have propagated to $p$. That did not happen, so this violating configuration is impossible. Hence all implications hold, and the constructed grid is valid. □

       Theorem.

       The first output grid is the unique valid structure with the minimum number of molecules, and the second output grid is the unique valid structure with the maximum number of molecules.

       Proof.

       By Lemma 1, every cell placed in the minimal grid is mandatory in every valid solution; by Lemma 2, that grid is valid. Therefore no valid solution can use fewer molecules.

       By Lemma 3, every cell removed from the maximal grid must be absent in every valid solution; by Lemma 4, the resulting grid is valid. Therefore no valid solution can use more molecules.

       Because the set of mandatory-present cells and the set of mandatory-absent cells are uniquely determined by the constraints, both extremal grids are unique. □

       Complexity Analysis

       Let $N = dx \cdot dy$ and let $k$ be the number of winds.

       • Building the forced sets takes $O(kN)$ time.

       • Each BFS marks every cell at most once and inspects all $k$ winds, so each BFS also takes $O(kN)$ time.

       • The total memory usage is $O(kN)$ for the boundary tables and $O(N)$ for the work arrays.

       Implementation Notes

       • The output order is row-major from $(1,1)$ in the top-left corner, exactly as requested in the statement.

       • The same per-wind boundary table is used both to propagate mandatory presence and to block reverse absence propagation through actual boundaries.