No.2536 Equivalence and Satisfiability
Note
After the contest ended, a statement was added specifying that the output format must be followed strictly.
Problem Statement
The input begins with $2$ positive integers $N, M$.
In a certain village live $N$ bots called equivalence-loving bots. They are numbered with the positive integers $i$ less than or equal to $N$, and each is called equivalence-loving bot $i$.
You are visiting the village, and you intend to choose at least half (that is, a number at least $\frac{N}{2}$) of the $N$ equivalence-loving bots and take them home with you. However, the equivalence-loving bots have a total of $M$ requests regarding how they are chosen, and you want to comply with all $M$ requests.
Each request of the equivalence-loving bots is represented as $(i,E,j)$ using positive integers $i,j$ less than or equal to $N$ satisfying $i < j$ and a string $E$ that is either <==> or <=/=>. The request $(i,E,j)$ is a request from the $2$ bots equivalence-loving bot $i$ and equivalence-loving bot $j$, saying:
- if $E$ is
<==>: "Please choose either both of us or neither of us." - if $E$ is
<=/=>: "Please choose only one of us (exactly $1$ bot)."
These are the possible meanings of a request.
Determine whether there exists a way to choose at least half of the $N$ equivalence-loving bots that complies with all $M$ requests, and if one exists, find one such way of choosing.
Background
For each positive integer $i$ less than or equal to $N$, let $P_i$ denote the proposition "you choose equivalence-loving bot $i$ and take it home". Each request $(i,E,j)$ can be expressed as the proposition $P_i \Leftrightarrow P_j$ if $E$ is <==>, and as the proposition $P_i \not\Leftrightarrow P_j$ if $E$ is <=/=>. This problem can be regarded as a problem about the satisfiability of the proposition obtained by joining with $\land$ a total of $M+1$ propositions: the $M$ propositions representing the requests and the proposition "you choose at least half of the $N$ equivalence-loving bots and take them home".
Now, let $I_N$ be the set of positive integers less than or equal to $N$, and let $U_N$ be the set of all subsets of $I_N$ with at least $2^{-1} N$ elements. Then for any $S \in U_N$, the proposition "the set of all numbers of the equivalence-loving bots you take home is $S$" can be expressed as $(\bigwedge_{i \in S} P_i) \land (\bigwedge_{i \in I_N \setminus S} (\neg P_i))$. Hence, the proposition "you choose at least half of the $N$ equivalence-loving bots and take them home" can be expressed as $\bigvee_{S \in U_N} ((\bigwedge_{i \in S} P_i) \land (\bigwedge_{i \in I_N \setminus S} (\neg P_i)))$.
From the above, this problem can be regarded as a problem about the satisfiability of the proposition formed by joining with $\land$ a total of $M+1$ propositions: the $M$ propositions obtained by applying $\Leftrightarrow$ or $\not\Leftrightarrow$ to propositional variables, and $\bigvee_{S \in U_N} ((\bigwedge_{i \in S} P_i) \land (\bigwedge_{i \in I_N \setminus S} (\neg P_i)))$.
Input
Below, for each positive integer $m$ less than or equal to $M$, the $m$-th request is denoted by $(i_m,E_m,j_m)$.
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 the components $i_m,E_m,j_m$ of the $m$-th request $(i_m,E_m,j_m)$, separated by single-byte spaces.
$N$ $M$ $i_1$ $E_1$ $j_1$ $\vdots$ $i_M$ $E_M$ $j_M$
Constraints
The input satisfies the following constraints:
- $N$ is an integer satisfying $2 \leq N \leq 10^5$.
- $M$ is an integer satisfying $1 \leq M \leq \min \{10^5,N(N-1)\}$.
- For any positive integer $m$ less than or equal to $M$:
- $i_m,j_m$ are integers satisfying $1 \leq i_m < j_m \leq N$.
- $E_m$ is a string that is either
<==>or<=/=>. - For any positive integers $\ell, m$ less than or equal to $M$, if $\ell \neq m$, then $(i_{\ell},E_{\ell},j_{\ell}) \neq (i_m,E_m,j_m)$.
Output
If there is no way to choose at least half of the $N$ equivalence-loving bots that complies with all $M$ requests, output No.
No
If such a way exists, output Yes on line $1$, and output an example of such a way of choosing on lines $2$ and $3$ in the following format:
- On line $2$, output the number $n$ of equivalence-loving bots you choose.
- On line $3$, output the numbers of the $n$ chosen equivalence-loving bots in ascending order, without duplicates, separated by single-byte spaces.
Yes $n$ (選ぶ同値大好きbotの番号のうち $1$ 番目に小さいもの) $\cdots$ (選ぶ同値大好きbotの番号のうち $n$ 番目に小さいもの)
This is a special judge problem. If there are multiple correct answers, you may output any of them.
However, follow the output format described above. For example, the behavior of the judge is not guaranteed if you add an extra space at the end of a line.
Print a newline at the end.
Sample
Sample 1
Input
2 1 1 <==> 2
Output
Yes 2 1 2
The requests made are the following
- The request from equivalence-loving bot $1$ and equivalence-loving bot $2$: "Please choose either both of us or neither of us."
only this $1$ request. You can comply with this request by choosing the $2$ bots equivalence-loving bot $1$ and equivalence-loving bot $2$, and $2$ is at least $2^{-1} N = 1$, half of $N = 2$. Note that, due to the constraints of the output format, outputting
Yes 2 2 1
is judged incorrect.
Sample 2
Input
2 2 1 <==> 2 1 <=/=> 2
Output
No
The requests made are the following
- The request from equivalence-loving bot $1$ and equivalence-loving bot $2$: "Please choose either both of us or neither of us."
- The request from equivalence-loving bot $1$ and equivalence-loving bot $2$: "Please choose only one of us."
these $2$ requests. As this shows, the equivalence-loving bots may make contradictory requests. There is no way of choosing that complies with all of these requests.
Sample 3
Input
3 2 1 <=/=> 2 2 <=/=> 3
Output
Yes 2 1 3
The requests made are the following
- The request from equivalence-loving bot $1$ and equivalence-loving bot $2$: "Please choose only one of us."
- The request from equivalence-loving bot $2$ and equivalence-loving bot $3$: "Please choose only one of us."
these $2$ requests. You can comply with these requests by choosing the $2$ bots equivalence-loving bot $1$ and equivalence-loving bot $3$, and $2$ is at least $2^{-1} N = 1.5$, half of $N = 3$.
Sample 4
Input
3 3 1 <==> 2 2 <==> 3 1 <=/=> 3
Output
No
The requests made are the following
- The request from equivalence-loving bot $1$ and equivalence-loving bot $2$: "Please choose either both of us or neither of us."
- The request from equivalence-loving bot $2$ and equivalence-loving bot $3$: "Please choose either both of us or neither of us."
- The request from equivalence-loving bot $1$ and equivalence-loving bot $3$: "Please choose only one of us."
these $3$ requests. There is no way of choosing that complies with all of these requests.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。