In this subtask, no overlaps are allowed so the optimal arrangement maximizes the number of ~2 \times 2~ houses. There are two cases:

• Case 1: ~M~ is even
  The optimal arrangement is to place ~2 \times 2~ houses that cover columns ~(1,2), (3,4), (5,6), \ldots, (M-1, M)~ and cover the remaining squares with ~1 \times 1~ houses. For each ~2 \times 2~ house, its top left corner could be in either row ~1~ or ~2~. Hence, the minimum number of houses required is ~\frac{3}{2}M~ and there are ~2^{\frac{M}{2}}~ possible arrangements. To optimize our computations, we can use binary exponentiation.
• Case 2: ~M~ is odd
  This case is similar to case 1, except that the optimal arrangement always has exactly one column that consists of ~3~ ~1 \times 1~ houses. Since we can insert this column between any of the ~2 \times 2~ houses, there are ~\lceil \frac{M}{2} \rceil~ possible placements. Hence, the minimum number of houses required is ~3\lceil \frac{M}{2} \rceil~ and there are ~\lceil \frac{M}{2} \rceil 2^{\frac{M-1}{2}}~ possible arrangements.

~\mathcal{O}(\log M)~

Since there is only ~1~ square that allows overlaps, the only way to utilize it is for two ~2 \times 2~ houses to share a corner square. Thus, this square must be in the interior. We also observe that an optimal arrangement only uses the overlap when ~M~ is odd. If these conditions are met, the minimum number of houses required is ~3\frac{M-3}{2}+4~ and there are ~2^{\frac{M-1}{2}}~ possible arrangements.

~\mathcal{O}(\log M)~

The intended solution is to use dynamic programming. One possible state is to store the minimum number of houses required and the number of arrangements that uses this number of houses for the first ~i~ columns, separating them by the types of houses used in the ~i^{\text{th}}~ column. To transition to the ~(i+1)^{\text{th}}~ column, we check if column ~i~ or ~i+1~ contain any squares allowing overlaps and account for them accordingly.

Subtask 3 was meant to reward partial points for erroneous solutions.

~\mathcal{O}(M)~

Instead of computing DP states for each column, we only need to compute them for columns containing a square that allows overlaps or columns that are adjacent to such squares. Then we can use our idea from subtask 1 to quickly compute the gap in between. Careful implementation is required to avoid over/undercounting.

~\mathcal{O}(K\log K)~