No.3047 Verification of Sorting Network
タグ : / 解いたユーザー数 4
作問者 :
amentorimaru
Problem Statement
There is a simple device called a "comparator". It compares the values of its $2$ inputs and outputs them so that the larger value is placed later. A "comparison network" built by combining such comparators, when properly constructed, becomes a "sorting network", which rearranges the input sequence and outputs a non-decreasing sequence.
Problem
You are given $T$ comparison networks. The $i$-th $(1\leq i\leq T)$ comparison network handles input and output sequences of length $N_i$ and consists of $M_i$ comparators $(A_{i,j},B_{i,j})$.
For the $i$-th comparison network, $N_i,M_i,(A_{i,j},B_{i,j})$ may be abbreviated as $N,M,(A_j,B_j)$, respectively.
For each of the given $T$ comparison networks, determine whether it is a "sorting network".
- If the comparison network is a "sorting network": considering every input sequence of length $N$, output in ascending order all comparator indices at which no swap is ever performed $j\ \ (1\leq j\leq M)$, that is, those for which $W[A_j]\leq W[B_j]$ always holds at time $j$ in the working sequence $W$ of the comparison network.
- If the comparison network is "not a sorting network": considering every input sequence of length $N$, output in ascending order all positions at which adjacent elements may fail to be in non-decreasing order $k\ \ (1\leq k\leq N-1)$, that is, those for which $Y[k]\gt Y[k+1]$ can occur in the output sequence $Y$ of the comparison network.
What is a comparator
- It has $2$ inputs and $2$ outputs.
- For inputs $(\alpha,\beta)$, if $\alpha\leq\beta$, it outputs $(\alpha,\beta)$.
- For inputs $(\alpha,\beta)$, if $\alpha\gt\beta$, it outputs $(\beta,\alpha)$.
What is a comparison network
- For comparators $1\leq j\leq M$, $1\leq A_{j}\lt B_{j}\leq N$
- The input sequence $X$ to the comparison network is a sequence consisting of the integers $\{1,2,\dots,N\}$ (this can be generalized to a sequence of elements of a linearly ordered (totally ordered) set)
- The input sequence $X$ is a sequence of length $N$, written as $X=[X[1],X[2],\dots,X[N]]$
- The working sequence $W$ is a sequence of length $N$, written as $W=[W[1],W[2],\dots,W[N]]$
- The output sequence $Y$ is a sequence of length $N$, written as $Y=[Y[1],Y[2],\dots,Y[N]]$
Taking the start time of processing as $0$, a comparison network operates as follows.
-
Time $0$ : Receive the input sequence $X$ and copy it to the working sequence $W$.
-
Time $1$ : Compare $W[A_{1}]$ and $W[B_{1}]$, and if $W[A_{1}]\gt W[B_{1}]$, swap the values of $W[A_{1}]$ and $W[B_{1}]$.
-
Time $2$ : Compare $W[A_{2}]$ and $W[B_{2}]$, and if $W[A_{2}]\gt W[B_{2}]$, swap the values of $W[A_{2}]$ and $W[B_{2}]$.
$\vdots$
-
Time $M$ : Compare $W[A_{M}]$ and $W[B_{M}]$, and if $W[A_{M}]\gt W[B_{M}]$, swap the values of $W[A_{M}]$ and $W[B_{M}]$.
-
Time $(M+1)$ : Copy the working sequence $W$ to the output sequence $Y$ and output it.
What is a sorting network
A "comparison network" that, for any input sequence $X$ of length $N$, always outputs a non-decreasing sequence $Y[1]\leq Y[2]\leq\dots\leq Y[N]$ is called a "sorting network".
Conversely, if there exists an input sequence for which the comparison network fails to output a non-decreasing sequence, that "comparison network" is "not a sorting network".
Constraints
- All input values are integers
- $1\leq T\leq 1000$
- $2\leq N_i\leq 27\quad(1\leq i\leq T)$
- $1\leq M_i\leq\cfrac{N_i(N_i-1)}{2}\quad(1\leq i\leq T)$
- $1\leq A_{i,j}\lt B_{i,j}\leq N_i\quad(1\leq i\leq T,\ 1\leq j\leq M_i)$
- $\sum_{i=1}^{T}(M_i\times\varphi^{N_i})\leq 10^{8}$
- $\varphi=\dfrac{1+\sqrt{5}}{2}\simeq 1.6180339887$
Input
The input is given from standard input in the following format. Here, $\mathrm{case}_i$ denotes the $i$-th test case.
$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$
Each test case is given in the following format.
$N\ M$ $A_1\ A_2\ A_3 \dots A_M$ $B_1\ B_2\ B_3 \dots B_M$
Output
Output $3$ lines per $1$ test case, for a total of $3T$ lines.
-
If you determine that the comparison network given in the $i$-th $(1\leq i\leq T)$ test case is a "sorting network", output $3$ lines as follows.
- On line $1$,
Yes - On line $2$, the number of applicable comparator indices $j$
- On line $3$, the applicable comparator indices $j$ in ascending order, separated by spaces (an empty line if the count is $0$)
- On line $1$,
-
If you determine that the comparison network given in the $i$-th $(1\leq i\leq T)$ test case is "not a sorting network", output $3$ lines as follows.
- On line $1$,
No - On line $2$, the number of applicable positions $k$
- On line $3$, the applicable positions $k$ in ascending order, separated by spaces
- On line $1$,
Sample
Sample 1
Input
4 2 1 1 2 4 5 1 3 1 2 2 2 4 3 4 3 4 6 1 3 1 2 2 3 2 4 3 4 3 4 4 5 1 3 2 1 3 2 4 3 2 4
Output
Yes 0 Yes 0 Yes 1 6 No 1 2
The figures below are schematic diagrams of comparison networks: the left end of each horizontal line represents an input and the right end represents an output. Vertical lines represent comparators.
In a comparison network, the output of every comparator is connected either to an output of the network or to an input of another comparator. Since a comparison network has the structure of a directed acyclic graph, there is no cycle that returns to the same comparator when tracing from outputs to inputs. For this reason, it can be drawn with values flowing from left to right, as in the figures.
-
The $1$st test case is the simplest $2$-input "sorting network".
2 1 1 2
$i=1,\ (N_1,M_1)=(2,1),\ [(A_{1,j},B_{1,j})]=[(1,2)]$
For example, if the integer sequences $[1,1],\ [2,2],\ [1,2],\ [2,1]$ are each input to this comparison network, the results are as follows.
-
If $X=[1,1]$ is input, this comparison network outputs the non-decreasing sequence $Y=[1,1]$.
-
If $X=[2,2]$ is input, this comparison network outputs the non-decreasing sequence $Y=[2,2]$.
-
If $X=[1,2]$ is input, this comparison network outputs the non-decreasing sequence $Y=[1,2]$.
-
If $X=[2,1]$ is input, this comparison network outputs the non-decreasing sequence $Y=[1,2]$.
For all input sequences of length $2$, this comparison network outputs a non-decreasing sequence. This comparison network is a "sorting network".
The $1$st output:
Yes 0
-
-
The $2$nd test case is an example of a $4$-input "sorting network".
4 5 1 3 1 2 2 2 4 3 4 3
$i=2,\ (N_2,M_2)=(4,5),\ [(A_{2,j},B_{2,j})]=[(1,2),(3,4),(1,3),(2,4),(2,3)]$
For example, if the integer sequence $X=[4,3,2,1]$ is input to this comparison network, the result is as follows.
- Time $0:$ In the initial state, the input sequence $X$ is copied, so $W=[4,3,2,1]$.
- Time $1:$ The $1,2$-th elements are compared, resulting in $W=[3,4,2,1]$.
- Time $2:$ The $3,4$-th elements are compared, resulting in $W=[3,4,1,2]$.
- Time $3:$ The $1,3$-th elements are compared, resulting in $W=[1,4,3,2]$.
- Time $4:$ The $2,4$-th elements are compared, resulting in $W=[1,2,3,4]$.
- Time $5:$ The $2,3$-th elements are compared, resulting in $W=[1,2,3,4]$.
- Time $6:$ $W=[1,2,3,4]$ is output as the output sequence $Y$.
For example, if the integer sequence $X=[4,2,3,1]$ is input to this comparison network, the result is as follows.
- Time $0:$ In the initial state, the input sequence $X$ is copied, so $W=[4,2,3,1]$.
- Time $1:$ The $1,2$-th elements are compared, resulting in $W=[2,4,3,1]$.
- Time $2:$ The $3,4$-th elements are compared, resulting in $W=[2,4,1,3]$.
- Time $3:$ The $1,3$-th elements are compared, resulting in $W=[1,4,2,3]$.
- Time $4:$ The $2,4$-th elements are compared, resulting in $W=[1,3,2,4]$.
- Time $5:$ The $2,3$-th elements are compared, resulting in $W=[1,2,3,4]$.
- Time $6:$ $W=[1,2,3,4]$ is output as the output sequence $Y$.
This comparison network is a "sorting network", which always outputs a non-decreasing sequence for the other input sequences of length $4$ as well.
The $2$nd output:
Yes 0
-
The $3$rd test case is also a "sorting network", but the $6$th comparator, drawn with a red line, never performs a swap for any input.
4 6 1 3 1 2 2 3 2 4 3 4 3 4
$i=3,\ (N_3,M_3)=(4,6),\ [(A_{3,j},B_{3,j})]=[(1,2),(3,4),(1,3),(2,4),(2,3),(3,4)]$
The $3$rd output:
Yes 1 6
-
The $4$th test case is a $4$-input comparison network, but it is "not a sorting network".
4 5 1 3 2 1 3 2 4 3 2 4
$i=4,\ (N_4,M_4)=(4,5),\ [(A_{4,j},B_{4,j})]=[(1,2),(3,4),(2,3),(1,2),(3,4)]$
For example, if the integer sequence $X=[4,3,2,1]$ is input to this comparison network, the result is as follows.
- Time $0:$ In the initial state, the input sequence $X$ is copied, so $W=[4,3,2,1]$.
- Time $1:$ The $1,2$-th elements are compared, resulting in $W=[3,4,2,1]$.
- Time $2:$ The $3,4$-th elements are compared, resulting in $W=[3,4,1,2]$.
- Time $3:$ The $2,3$-th elements are compared, resulting in $W=[3,1,4,2]$.
- Time $4:$ The $1,2$-th elements are compared, resulting in $W=[1,3,4,2]$.
- Time $5:$ The $3,4$-th elements are compared, resulting in $W=[1,3,2,4]$.
- Time $6:$ $W=[1,3,2,4]$ is output as the output sequence $Y$.
Since $[1,3,2,4]$ is not sorted in non-decreasing order, the comparison network given in the $4$th test case is not a "sorting network".
Since $Y[2]\gt Y[3]$, for this input sequence $Y[k]\gt Y[k+1]$ holds when $k=2$. Moreover, for any input sequence of length $N_i$, $Y[k]\gt Y[k+1]$ does not hold when $k\neq 2$, so we output that $Y[k]\gt Y[k+1]$ can hold only at the position marked with a red dot, $k=2$.
The $4$th output:
No 1 2
Sample 2
Input
4 8 28 1 3 5 7 2 4 6 1 3 5 7 2 4 6 1 3 5 7 2 4 6 1 3 5 7 2 4 6 2 4 6 8 3 5 7 2 4 6 8 3 5 7 2 4 6 8 3 5 7 2 4 6 8 3 5 7 8 24 1 3 5 7 1 2 5 6 1 3 5 7 1 2 3 4 1 2 5 6 1 3 5 7 2 4 6 8 4 3 8 7 2 4 6 8 8 7 6 5 3 4 7 8 2 4 6 8 8 19 1 3 5 7 1 2 5 6 2 6 1 2 3 4 3 4 2 4 6 2 4 6 8 3 4 7 8 3 7 5 6 7 8 5 6 3 5 7 8 19 1 3 5 7 1 5 2 6 1 2 3 4 3 4 2 4 2 4 6 2 4 6 8 3 7 4 8 5 6 7 8 5 6 5 7 3 5 7
Output
Yes 0 Yes 0 Yes 0 Yes 0
All of these comparison networks are "sorting networks", which always sort the input sequence into non-decreasing order and output it.
Odd-even transposition sort
Bitonic sort
Batcher's odd-even merge sort
Pairwise sort
Sample 3
Input
2 26 142 1 3 5 7 9 11 13 15 17 19 21 23 25 1 2 5 6 9 10 15 16 19 20 23 24 1 2 3 4 9 10 11 12 13 19 20 21 22 1 2 3 4 5 6 7 8 9 11 12 14 2 3 4 5 6 7 8 10 12 14 16 18 1 2 4 6 7 8 9 11 13 15 17 22 3 4 6 9 11 14 15 17 22 2 4 7 8 10 13 15 16 18 22 2 4 5 8 9 10 12 14 16 20 21 24 3 5 6 8 12 13 16 17 20 23 4 6 8 10 12 14 16 18 20 22 6 7 10 11 14 15 18 19 5 7 9 11 13 15 17 19 21 2 4 6 8 10 12 14 16 18 20 22 24 26 3 4 7 8 11 12 17 18 21 22 25 26 5 6 7 8 15 17 14 18 16 23 24 25 26 19 20 21 22 23 24 25 26 13 15 16 18 19 11 21 9 23 15 25 13 20 17 24 22 5 10 14 16 19 20 12 21 23 18 25 26 5 12 10 18 13 16 23 21 24 5 9 11 14 12 19 17 20 23 25 3 7 6 13 11 15 17 19 18 23 22 25 4 7 11 10 14 15 21 19 22 24 5 7 9 11 13 15 17 19 21 23 8 9 12 13 16 17 20 21 6 8 10 12 14 16 18 20 22 26 177 1 3 5 7 9 11 15 17 19 21 23 25 1 2 5 6 9 10 15 16 19 20 23 24 13 22 6 4 8 12 17 2 14 3 10 18 1 9 8 5 11 16 15 7 6 2 18 19 1 25 15 19 3 13 23 10 5 14 4 9 20 1 7 16 13 17 22 8 21 6 3 12 2 1 24 15 19 10 12 14 18 4 7 23 2 3 20 9 13 11 16 18 8 21 5 4 23 2 25 10 15 12 17 8 20 6 11 22 4 24 1 15 13 17 10 19 7 21 5 3 23 16 13 9 18 11 7 20 4 22 2 24 14 11 12 8 19 10 6 21 4 2 23 14 12 17 10 7 20 15 5 22 3 14 11 18 16 9 6 21 4 23 15 13 19 17 8 10 5 12 16 14 20 18 7 9 4 2 4 6 8 10 12 16 18 20 22 24 26 3 4 7 8 11 12 17 18 21 22 25 26 15 23 16 9 25 19 21 11 24 5 20 26 7 22 10 17 13 24 21 14 12 3 20 23 4 26 18 21 7 17 24 12 6 16 8 11 22 2 15 19 14 18 23 10 25 9 4 20 11 5 26 17 21 11 13 16 22 9 8 25 5 6 24 10 15 12 17 20 14 22 6 7 24 3 26 13 18 14 19 9 21 7 16 23 5 25 2 16 14 18 11 20 9 22 6 4 24 17 15 10 19 12 8 21 6 23 5 25 17 13 15 9 20 16 7 22 5 3 24 16 13 18 11 8 21 19 6 23 4 15 12 19 17 10 7 22 5 24 16 14 20 18 9 11 6 13 17 15 21 19 8 10 5
Output
Yes 1 78 No 7 3 6 11 13 15 19 21
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。