P8420 [THUPC 2022 Finals] Matching

A “match item” is defined as a string of length $L$, where each position is either $\texttt{0}$ or $\texttt{1}$. Now there are $N$ such “match items”. We want to design a “plan”, which is also a string of length $L$, and each position is either $\texttt{0}$ or $\texttt{1}$. For each “match item”, define its error value as the number of positions where the “plan” differs from the “match item”. For example, if the “match item” is $\texttt{101}$ and the “plan” is $\texttt{000}$, then the first and third positions are different, so the error value of this “plan” for that “match item” is $2$. We want to find a “plan” that minimizes the sum of error values over these $N$ “match items”. In addition, there are $M$ distinct forbidden “plans”, and the “plan” we find must not be one of the forbidden “plans”.

The first line contains three positive integers $N, M, L$. Then there are $N$ lines, each being a string of length $L$. After that, there are $M$ lines, each being a string of length $L$.

Output one integer, the minimum possible sum of error values over the $N$ “match items” achieved by a valid “plan”.

It is guaranteed that $1 \le N \le 1000$, $1 \le M \le \min(1000, 2^L - 1)$, $1 \le L \le 1000$. Translated by ChatGPT 5