A - Flip Row or Col 2 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 800 点

問題文

N\times N 行列 A=(A_{i,j})\ (1\leq i,j\leq N) および長さ N の整数列 R=(R_1,R_2,\ldots,R_N), C=(C_1,C_2,\ldots,C_N) が与えられます． A の各要素は 0 または 1 であり，R,C の各要素は 0 以上 \frac{N}{4} 未満です．

あなたは 0 および 1 からなる長さ N の文字列の組 X,Y を自由に選ぶことができます．選んだ文字列 X,Y をもとに以下の操作を行います．

  • まず，各 i=1,2,\ldots,N に対して以下を行う．X_i を X の i 文字目として，
    • X_i が 0 のとき，なにもしない．
    • X_i が 1 のとき，A の i 行目の要素を全て反転する．すなわち，各 j=1,2,\ldots,N に対して A_{i,j} を 1-A_{i,j} で置き換える．
  • 次に，各 j=1,2,\ldots,N に対して以下を行う．Y_j を Y の j 文字目として，
    • Y_j が 0 のとき，なにもしない．
    • Y_j が 1 のとき，A の j 列目の要素を全て反転する．すなわち，各 i=1,2,\ldots,N に対して A_{i,j} を 1-A_{i,j} で置き換える．

X,Y をうまく選ぶことで操作後の A が以下の条件を満たすことが可能かどうか判定し，可能ならばそのような組を一つを出力してください．

  • 各 i=1,2,\ldots,N に対して，A の i 行目の要素の総和 \displaystyle \sum_{j=1}^N A_{i,j} は R_i である．
  • 各 j=1,2,\ldots,N に対して，A の j 列目の要素の総和 \displaystyle \sum_{i=1}^N A_{i,j} は C_j である．

T 個のテストケースが与えられるので，それぞれについて答えてください．

制約

  • 1\leq T\leq 10^5
  • 1\leq N\leq 1000
  • A_{i,j} \in\lbrace 0,1\rbrace
  • 0\leq R_i,C_j\lt \frac{N}{4}
  • T,N,R_i,C_j は整数
  • 1 つの入力ファイルに含まれる N^2 の総和は 10^6 以下

入力

入力は以下の形式で標準入力から与えられる．

T
\textrm{case}_1
\textrm{case}_2
\vdots
\textrm{case}_T

各テストケースは以下の形式で与えられる．

N
A_{1,1}A_{1,2}\dots A_{1,N}
A_{2,1}A_{2,2}\dots A_{2,N}
\vdots
A_{N,1}A_{N,2}\dots A_{N,N}
R_1 R_2 \ldots R_N
C_1 C_2 \ldots C_N

出力

\textrm{case}_1,\textrm{case}_2,\ldots,\textrm{case}_T に対する答えを順に以下の形式で出力せよ．

条件を満たす X,Y の組が存在しなければ No と出力せよ．

存在する場合，

Yes
X
Y

と出力せよ．解が複数存在する場合，どれを出力しても正解とみなされる．

入力例 1

3
2
10
01
0 0
0 0
5
10101
11110
01111
10011
00110
1 1 1 1 1
1 1 1 1 1
10
0001011010
0101101000
0000101111
0010011100
0111000001
0011100110
1110001110
1100110000
0110111011
1101101101
1 1 0 2 0 0 2 2 2 2
2 2 0 1 0 2 1 2 1 1

出力例 1

Yes
01
10
Yes
01101
10001
No

1 つ目のテストケースについて，A=\begin{pmatrix}1&0 \\ 0&1\end{pmatrix} です． X,Y がそれぞれ 01, 10 の場合を考えます．操作は次のように行われます．

  • X_1 は 0 なのでなにもしません．
  • X_2 は 1 なので A の 2 行目の要素を反転して A=\begin{pmatrix}1&0 \\ 1&0\end{pmatrix} となります．
  • Y_1 は 1 なので A の 1 列目の要素を反転して A=\begin{pmatrix}0&0 \\ 0&0\end{pmatrix} となります．
  • Y_2 は 0 なのでなにもしません．

したがって，操作後の A は A=\begin{pmatrix}0&0 \\ 0&0\end{pmatrix} です．A の 1 行目の要素の総和，2 行目の要素の総和，1 列目の要素の総和，2 列目の要素の総和は全て 0 であるため，条件を満たします．

他にも

Yes
10
01

と出力しても正解となります．

Score : 800 points

Problem Statement

You are given an N\times N matrix A=(A_{i,j})\ (1\leq i,j\leq N) and integer sequences of length N: R=(R_1,R_2,\ldots,R_N), C=(C_1,C_2,\ldots,C_N). Each element of A is 0 or 1, and each element of R,C is at least 0 and less than \frac{N}{4}.

You can freely choose a pair of strings X,Y of length N consisting of 0 and 1. Based on the chosen strings X,Y, perform the following operations:

  • First, for each i=1,2,\ldots,N, do the following. Let X_i be the i-th character of X:
    • If X_i is 0, do nothing.
    • If X_i is 1, flip all elements in the i-th row of A. That is, for each j=1,2,\ldots,N, replace A_{i,j} with 1-A_{i,j}.
  • Next, for each j=1,2,\ldots,N, do the following. Let Y_j be the j-th character of Y:
    • If Y_j is 0, do nothing.
    • If Y_j is 1, flip all elements in the j-th column of A. That is, for each i=1,2,\ldots,N, replace A_{i,j} with 1-A_{i,j}.

Determine whether it is possible to choose X,Y cleverly so that the matrix A after the operations satisfies the following conditions, and if possible, output one such pair.

  • For each i=1,2,\ldots,N, the sum of elements in the i-th row of A, \displaystyle \sum_{j=1}^N A_{i,j}, is R_i.
  • For each j=1,2,\ldots,N, the sum of elements in the j-th column of A, \displaystyle \sum_{i=1}^N A_{i,j}, is C_j.

You are given T test cases, so answer each of them.

Constraints

  • 1\leq T\leq 10^5
  • 1\leq N\leq 1000
  • A_{i,j} \in\lbrace 0,1\rbrace
  • 0\leq R_i,C_j\lt \frac{N}{4}
  • T,N,R_i,C_j are integers.
  • The sum of N^2 over all test cases in one input file is at most 10^6.

Input

The input is given from Standard Input in the following format:

T
\textrm{case}_1
\textrm{case}_2
\vdots
\textrm{case}_T

Each test case is given in the following format:

N
A_{1,1}A_{1,2}\dots A_{1,N}
A_{2,1}A_{2,2}\dots A_{2,N}
\vdots
A_{N,1}A_{N,2}\dots A_{N,N}
R_1 R_2 \ldots R_N
C_1 C_2 \ldots C_N

Output

Output your solutions for \textrm{case}_1,\textrm{case}_2,\ldots,\textrm{case}_T in order in the following format:

If there is no pair X,Y that satisfies the conditions, output No.

If there exists such a pair, output:

Yes
X
Y

If there are multiple solutions, any of them will be considered correct.

Sample Input 1

3
2
10
01
0 0
0 0
5
10101
11110
01111
10011
00110
1 1 1 1 1
1 1 1 1 1
10
0001011010
0101101000
0000101111
0010011100
0111000001
0011100110
1110001110
1100110000
0110111011
1101101101
1 1 0 2 0 0 2 2 2 2
2 2 0 1 0 2 1 2 1 1

Sample Output 1

Yes
01
10
Yes
01101
10001
No

For the first test case, A=\begin{pmatrix}1&0 \\ 0&1\end{pmatrix}. Consider the case where X,Y are 01 and 10, respectively. The operations are performed as follows:

  • X_1 is 0, so do nothing.
  • X_2 is 1, so flip the elements in the 2nd row of A, resulting in A=\begin{pmatrix}1&0 \\ 1&0\end{pmatrix}.
  • Y_1 is 1, so flip the elements in the 1st column of A, resulting in A=\begin{pmatrix}0&0 \\ 0&0\end{pmatrix}.
  • Y_2 is 0, so do nothing.

Therefore, the matrix A after the operations is A=\begin{pmatrix}0&0 \\ 0&0\end{pmatrix}. The sum of elements in the 1st row, the sum of elements in the 2nd row, the sum of elements in the 1st column, and the sum of elements in the 2nd column are all 0, so the conditions are satisfied.

It would also be correct to output:

Yes
10
01