No.3311 Filter
Problem Statement
A string consisting only of the digits $0$ and $1$ is called a bit string.
You are given as input $2$ positive integers $N, M$ and a set $S$ with $M$ elements, consisting only of bit strings of length $N$.
The bitwise AND of bit strings of length $N$ is denoted by $\textrm{AND}$. $S$ is called a good bit string set if it satisfies all of the following $3$ conditions:
- The string of length $N$ consisting only of the digit $0$ is not an element of $S$.
- For any bit string $s_0$ of length $N$ and any element $s_1$ of $S$, if $s_0 \textrm{ AND } s_1 = s_1$, then $s_0$ is an element of $S$.
- For any elements $s_0$ and $s_1$ of $S$, $s_0 \textrm{ AND } s_1$ is an element of $S$.
Determine whether $S$ is a good bit string set.
Background
Let $I_N$ be the set of all positive integers less than or equal to $N$. For each $s \in S$, let $U_s$ be the set of all $i \in I_N$ satisfying the condition "the $i$-th character from the right of $s$ is $1$". By letting $\mathcal{F}_S$ be the family of sets $\{U_s \mid s \in S\}$, we can translate $S$ into the family $\mathcal{F}_S$ of subsets of $I_N$.
In set theory, topology, the theory of ordered sets, lattice theory and so on, the concept of a filter is often used. The property that $S$ is a good bit string set is equivalent to $\mathcal{F}_S$ being a filter on $I_N$, so this problem is essentially the problem of determining whether $\mathcal{F}_S$ is a filter on $I_N$.
Input
Number the elements of $S$ with the positive integers $m$ less than or equal to $M$, and denote them by $s_m$.
Then, the input is given from standard input in $1 + M$ lines in the following format:
- Line $1$ contains $N, M$ separated by a single-byte space.
- For each positive integer $m$ less than or equal to $M$, line $1 + m$ contains $s_m$.
$N$ $M$ $s_1$ $\vdots$ $s_M$
Constraints
The input satisfies the following constraints:
- $N$ is an integer satisfying $1 \leq N \leq 20$.
- $M$ is an integer satisfying $1 \leq M \leq \min \{2^N,10^5\}$.
- For any positive integer $m$ less than or equal to $M$, $s_m$ is a bit string of length $N$.
- For any positive integers $m_0, m_1$ less than or equal to $M$, if $m_0 \neq m_1$, then $s_{m_0} \neq s_{m_1}$.
Output
Print Yes if $S$ is a good bit string set, and No otherwise.
Print a newline at the end.
Sample
Sample 1
Input
1 1 0
Output
No
We have $S = \{0\}$, and in particular the string $0$ of length $N = 1$ consisting only of the digit $0$ is an element of $S$. Therefore condition 1 is violated, and $S$ is not a good bit string set.
Sample 2
Input
1 1 1
Output
Yes
We have $S = \{1\}$, and:
- The string $0$ of length $N = 1$ consisting only of the digit $0$ is not an element of $S$.
- For any bit string $s_0$ of length $N = 1$ and any element $s_1$ of $S$, since $s_1 = 1$, we have $s_0 \textrm{ AND } s_1 = s_0$. Therefore, if $s_0 \textrm{ AND } s_1 = s_1$, then $s_0 = 1$, which is an element of $S$.
- For any elements $s_0$ and $s_1$ of $S$, since $s_0 = s_1 = 1$, we have $s_0 \textrm{ AND } s_1 = 1$, which is an element of $S$.
Hence $S$ is a good bit string set.
Sample 3
Input
2 1 10
Output
No
We have $S = \{10\}$. Letting $(s_0,s_1) = (11,10)$, $s_0$ is a bit string of length $N = 2$ and $s_1$ is an element of $S$. Furthermore, $s_0 \textrm{ AND } s_1 = s_1$ holds, but $s_0$ is not an element of $S$. Therefore condition 2 is violated, and $S$ is not a good bit string set.
Sample 4
Input
2 1 11
Output
Yes
We have $S = \{11\}$, and:
- The string $00$ of length $N = 2$ consisting only of the digit $0$ is not an element of $S$.
- Let $s_0$ be a bit string of length $N = 2$ and let $s_1$ be an element of $S$. Then, since $s_1 = 11$, we have $s_0 \textrm{ AND } s_1 = s_0$. Therefore, if $s_0 \textrm{ AND } s_1 = s_1$, then $s_0 = 11$, which is an element of $S$.
- Let $s_0$ and $s_1$ be elements of $S$. Then, since $s_0 = s_1 = 11$, we have $s_0 \textrm{ AND } s_1 = 11$, which is an element of $S$.
Hence $S$ is a good bit string set.
Sample 5
Input
2 2 01 11
Output
Yes
We have $S = \{01,11\}$, and:
- The string $00$ of length $N = 2$ consisting only of the digit $0$ is not an element of $S$.
- Let $s_0$ be a bit string of length $N = 2$ and let $s_1$ be an element of $S$. Then $s_1$ is either $01$ or $11$. If $s_0 \textrm{ AND } s_1 = s_1$, then $s_0$ is either $01$ or $11$ when $s_1 = 01$, and $s_0$ is $11$ when $s_1 = 11$. Therefore, in either case, $s_0$ is an element of $S$.
- Let $s_0$ and $s_1$ be elements of $S$. Then there are $4$ possibilities for $(s_0,s_1)$: $(01,01),(01,11),(11,01),(11,11)$, and in each case $s_0 \textrm{ AND } s_1$ is $01,01,01,11$, respectively. Therefore, in every case, $s_0 \textrm{ AND } s_1$ is an element of $S$.
Hence $S$ is a good bit string set.
Sample 6
Input
2 2 01 10
Output
No
We have $S = \{01,10\}$. Letting $(s_0,s_1) = (01,10)$, $s_0$ and $s_1$ are elements of $S$. On the other hand, $s_0 \textrm{ AND } s_1 = 00$ is not an element of $S$. Therefore condition 3 is violated, and $S$ is not a good bit string set.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。