Flip Row or Col 2

AtCoder

IDarc199_a

Time2000ms

Memory256MB

Difficulty—

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$ [samples]

Samples

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

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 $2$nd row of $A$, resulting in $A=\begin{pmatrix}1&0 \\ 1&0\end{pmatrix}$.
*   $Y_1$ is `1`, so flip the elements in the $1$st 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 $1$st row, the sum of elements in the $2$nd row, the sum of elements in the $1$st column, and the sum of elements in the $2$nd column are all $0$, so the conditions are satisfied.
It would also be correct to output:

Yes
10
01

API Response (JSON)

{
  "problem": {
    "name": "Flip Row or Col 2",
    "description": {
      "content": "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 ",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc199_a"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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 ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments