No.2270 T0 Space
Note
This problem has a strict time limit and a large input size, so we recommend using a language and implementation capable of fast input and output.
The writer's solution takes 247[ms] in c++, 1879[ms] in PyPy3, and 4489[ms] in Python3 (that is, TLE ).
Problem Statement
You are given as input $2$ positive integers $N, M$ and a set $S$ with $M$ elements satisfying the following condition:
- Every element of $S$ is a string of length $N$ consisting only of the digits $0$ and $1$.
First, let us introduce a term. We say that $S$ is a good bit string set if, for any positive integers $n_0$ and $n_1$ not exceeding $N$, the following condition holds whenever $n_0 \neq n_1$:
- There exists $s \in S$ such that the $n_0$-th character from the right and the $n_1$-th character from the right of $s$ differ.
Determine whether $S$ is a good bit string set.
Background
Let $I_N$ be the set of all positive integers not exceeding $N$, for each $s \in S$ let $U_s$ be the set of all $i \in I_N$ satisfying "the $i$-th character from the right of $s$ is $1$", and let $\mathcal{O}_S$ be the family of sets $\{U_s \mid s \in S\}$. In this way, $S$ can be translated into the family $\mathcal{O}_S$ of subsets of $I_N$.
When geometry is formulated in modern set theory, the concept of a topological space is often used. When the pair $(I_N,\mathcal{O}_S)$ is a topological space, the property that $S$ is a good bit string set is called the $\textrm{T}_0$ property or Kolmogorov property of the topological space $(I_N,\mathcal{O}_S)$.
The $\textrm{T}_0$ property is one of the properties of topological spaces known as separation axioms, and it is a very weak property among the commonly used separation axioms. One commonly used property stronger than the $\textrm{T}_0$ property is the one called the $\textrm{T}_2$ property or Hausdorff property, which is frequently assumed when topological spaces are dealt with in geometry.
Input
Number the elements of $S$ by the positive integers $m$ not exceeding $M$, and denote them by $s_m$.
Then, the input is given from standard input in $2 + M$ lines in the following format:
- Line $1$ contains $N$.
- Line $2$ contains $M$.
- For each positive integer $m$ not exceeding $M$, line $2 + m$ contains $s_m$.
Constraints
The input satisfies the following constraints:
- $N$ is an integer satisfying $1 \leq N \leq 2^8$.
- $M$ is an integer satisfying $1 \leq M \leq \min \{2^N,2^{16}\}$.
- For any positive integer $m$ not exceeding $M$, $s_m$ is a string of length $N$ consisting only of the digits $0$ and $1$.
- For any positive integers $m_0, m_1$ not exceeding $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
Yes
Since there is no pair of $2$ distinct positive integers not exceeding $N = 1$, $S = \{0\}$ is a good bit string set.
For those familiar with topological spaces: $(I_N,\mathcal{O}_S) = (\{1\},\{\{\}\})$ does not satisfy $I_N \in \mathcal{O}_S$, so it is not a topological space. Therefore, $S$ being a good bit string set is not equivalent to $(I_N,\mathcal{O}_S)$ being a $\textrm{T}_0$ topological space.
Sample 2
Input
1 2 0 1
Output
Yes
Since there is no pair of $2$ distinct positive integers not exceeding $N = 1$, $S = \{0,1\}$ is a good bit string set.
For those familiar with topological spaces: $(I_N,\mathcal{O}_S) = (\{1\},\{\{\},\{1\}\})$ is both a discrete topological space and an indiscrete topological space.
For those familiar with algebraic geometry: $(I_N,\mathcal{O}_S)$ is a topological space homeomorphic to the affine scheme $\textrm{Spec}(\mathbb{Q}_p)$ associated with the field $\mathbb{Q}_p$ of $p$-adic numbers.
Sample 3
Input
2 1 11
Output
No
There is the pair $(n_0,n_1) := (1,2)$ of $2$ distinct positive integers not exceeding $N = 2$. On the other hand, $S = \{11\}$ has only the element $s := 11$, and the $n_0$-th character from the right and the $n_1$-th character from the right of $s$ are both equal to $1$, so $S$ is not a good bit string set.
Sample 4
Input
2 3 00 01 11
Output
Yes
Ignoring order, the only pair of $2$ distinct positive integers not exceeding $N = 2$ is $(n_0,n_1) := (1,2)$. Since the element $s := 01$ of $S = \{00,01,11\}$ differs at its $n_0$-th and $n_1$-th characters, $S$ is a good bit string set.
For those familiar with topological spaces: $(I_N,\mathcal{O}_S) = (\{1,2\},\{\{\},\{1\},\{1,2\}\})$ is a $\textrm{T}_0$ topological space that is not a discrete topological space.
For those familiar with algebraic geometry: $(I_N,\mathcal{O}_S)$ is a topological space homeomorphic to the affine scheme $\textrm{Spec}(\mathbb{Z}_p)$ associated with the ring $\mathbb{Z}_p$ of $p$-adic integers.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
MasKoaTS