\begin{tutorial}{Moving}

\begin{center}
\textit{Problem author: Alexander Babin, developer: Ivan Piskarev}
\end{center}

\section*{$O(S! \cdot S)$}
Let us iterate over all possible ways to perform the relocation and choose the best one.

\section*{$O(S^3 \cdot \log m)$}
We will search for the answer using binary search.
We want to check whether it is possible to organize the relocation so that the maximum distance is at most $k$.
Let us build a bipartite graph where the vertices in the left part correspond to places before the relocation, and the vertices in the right part correspond to places after the relocation.
There is an edge between two vertices if the distance between their houses does not exceed $k$.
It is easy to see that a relocation with distance at most $k$ is possible if and only if the graph contains a perfect matching.

A maximum matching in a bipartite graph can be found with Kuhn's algorithm in $O(nm)$, where $n$ is the number of vertices and $m$ is the number of edges.

\section*{$O(2^A \cdot AB)$}

Instead of explicitly finding a maximum matching, it is enough just to check Hall's lemma condition.
Namely, to check that for every subset $X$ of vertices in the left part, at least $|X|$ vertices in the right part are directly connected to it.
Since such a set of vertices in the right part depends only on the set of cells containing the vertices of the set $X$, it is enough to consider only $2^A$ variants of such a set.

\section*{$O(m)$ for $n = 1$}

Let us sort the places before the relocation and the places after the relocation by increasing $j$-coordinate.
Notice that the relocation method
where the resident from the $k$-th place before the relocation moves to the $k$-th place after the relocation is optimal.
The maximum distance for such a relocation method can be found with a two-pointers pass.

% \pagebreak % delete later

\section*{$O(m \cdot \log m)$ for $n \le 2$}




Let us do binary search on the answer.
We want to check whether it is possible to organize the relocation so that the maximum distance is at most $k$.
To do this, we will check Hall's lemma condition.

$ $

Let $X$ be a subset of houses.
\begin{itemize}
    \item
          Let $W_1(X)$ and $W_2(X)$ denote the total number of residents in $X$ before and after the relocation, respectively.
    \item
          Let $N(X)$ denote the set of houses at distance at most $k$ from $X$.
\end{itemize}

Then Hall's lemma condition is equivalent to the inequality $W_2(N(X)) - W_1(X) \ge 0$ holding for all $X$.
To check this, let us find the minimum value of $f(X) = W_2(N(X)) - W_1(X)$ and compare it with zero.

To find the minimum value, we use dynamic programming:
let \texttt{dp[i][mask]} be the minimum value of $f(X)$ if
\begin{itemize}
    \item $X$ consists only of houses up to the $i$-th column inclusive
    \item $X$ contains at least one house in the $i$-th column
    \item \texttt{mask} is the intersection of $X$ with the $i$-th column
          % \item Only houses up to the $i$-th column inclusive are counted in $W_2$
\end{itemize}

Notice that if $X$ contains at least one house in the $i$-th column, then whether a house strictly to the right of the $i$-th column belongs to $N(X)$ does not depend on whether houses strictly to the left of the $i$-th column belong to $X$, and vice versa.
Therefore, for the transition it is enough to iterate over the nearest house to the right that will be added to $X$.

Notice that it is enough to transition only to columns that are $1$ and $2k$ houses to the right.
Indeed, when transitioning by at most $2k - 1$ columns, including all skipped columns into $X$ will not make the answer worse, and therefore such a transition will be no worse than several transitions one column to the right.
And when transitioning by more than $2k$ columns, if the value of \texttt{dp} is at least $0$, it is not beneficial to use it, while if the value is negative, then a counterexample to Hall's lemma condition has already been found.


\section*{$O(m)$ for $n \le 2$}

Binary search can be removed.
Notice that after merging the first and second rows, the answer either does not change or decreases by one (since the distance between any two places either does not change or decreases by one).
Therefore, it is enough to solve the same problem for $n$ decreased by one and then perform a check for a single value of $k$.



% \section*{$O(m  \cdot n^2 \cdot 3^{2n})$}
\section*{Full solution $O(mn^2 \cdot 3^{2n})$}

Suppose we have $\mathbb{N}$ paints of different colors, numbered $0, 1, 2, ...$.


Let us introduce several definitions:

\begin{itemize}
    \item For a set of houses $X$, define the coloring of houses $C(X)$ in which each house is painted with the color whose number equals the distance to the nearest house from $X$.
    \item For a coloring of houses $C$, define the sets of houses $X(C), Y(C)$ consisting of houses of color $0$ and houses of colors $0, 1, 2, ..., k$ respectively.
    \item Define the cost of a coloring $C$ as $f(C) = W_2(Y(C)) - W_1(X(C))$.
    \item Call a coloring good if the difference between the color numbers of any two neighboring houses does not exceed $1$.
\end{itemize}

Notice that

\begin{itemize}
    \item $f(X) = f(C(X))$
    \item $C(X)$ is a good coloring
    \item If $C$ is a good coloring, then $f(C) \ge f(X(C))$
\end{itemize}

In the previous solution, we reduced the problem to computing $\displaystyle \min_X f(X)$.

Notice that the three properties above imply that $\displaystyle \min_X f(X) = \min_{C \text{ good}} f(C)$.

Therefore, it is enough to learn how to compute $\displaystyle \min_{C \text{ good}} f(C)$.



To do this, let us redefine \texttt{dp[i][mask]} as the minimum value of $f(C)$ over all good colorings $C$ such that
\begin{itemize}
    \item In $W_1, W_2$, only residents of houses up to the $i$-th column inclusive are counted
    \item \texttt{mask} encodes the color numbers of the houses in the $i$-th column
\end{itemize}

\subsection*{Transition in $O(m^2n \cdot 3^{2n})$}

Let us first try to simply compute \texttt{dp[i+1]} from \texttt{dp[i]}.

Notice that it makes no sense to consider colorings without color $0$, so the maximum color does not exceed $n + m = O(m)$.
Notice that if the color of the first house in a column is fixed, then the remaining ones can be colored in at most $3^{n-1}$ ways so that the coloring remains good.

Therefore, the number of possible values of \texttt{mask} is at most $O(m \cdot 3^n)$.

Notice that from \texttt{dp[i][mask]} we can transition to at most $3^n$ states in \texttt{dp[i+1]}.

One transition from \texttt{dp[i][mask1]} to \texttt{dp[i+1][mask2]} can obviously be done in $O(n)$.

In total, we have $O(m^2 \cdot 3^n)$ \texttt{dp} states, and from each of them we make at most $3^n$ transitions, each taking $O(n)$.
Therefore, the running time of such a solution is $O(m^2 \cdot n \cdot 3^{2n})$.


Notice that it is enough to consider only colorings using colors $0, 1, ..., \text{k}, \text{k} + 1$.
This allows solving the problem in $O(\text{ans} \cdot mn \cdot 3^{2n})$.

\subsection*{Transition in $O(mn^2 \cdot 3^{2n})$}

We will explicitly store only those states where color $0$ is present in \texttt{mask}.
Notice that the number of such values of \texttt{mask} is exactly $3^{n-1}$ (we choose $n-1$ differences between neighboring cells from $\left\{-1, 0, +1\right\}$ and add a constant so that the minimum becomes zero).

Notice that it is enough to transition only by $1,2, ..., 2n$ or $2k - 2 (n - 1), ..., 2k - 1, 2k$ columns to the right.
Suppose we transitioned from column $i_1$ to column $i_2$.
If $i_2 - i_1 < 2k - 2(n-1)$, then by adding columns from $i_1 + n$ to $i_2 - n$ to the set $X$, we will not increase the cost, because $Y(C)$ will remain the same.
If, on the other hand, $i_2 - i_1 > 2k$, then if the value of \texttt{dp} is negative (taking into account residents in columns to the right of $i_1$), we can already stop, and if it is at least zero, then it is not beneficial to use it in the transition.

Thus, we have $m \cdot 3^{n-1}$ states, and from each state we make at most $4n \cdot 3^{n-1}$ transitions, each of which is done in $O(n)$.



\end{tutorial}
