Anti-Increasing Addicts
Contest: Codeforces Global Round 22
Difficulty rating: 2900
Tags: constructive algorithms, dp, greedy, math

You are given an $$$n \times n$$$ grid.

We write $$$(i, j)$$$ to denote the cell in the $$$i$$$-th row and $$$j$$$-th column. For each cell, you are told whether yon can delete it or not.

Given an integer $$$k$$$, you are asked to delete exactly $$$(n-k+1)^2$$$ cells from the grid such that the following condition holds.

- You cannot find $$$k$$$ not deleted cells $$$(x_1, y_1), (x_2, y_2), \dots, (x_k, y_k)$$$ that are strictly increasing, i.e., $$$x_i < x_{i+1}$$$ and $$$y_i < y_{i+1}$$$ for all $$$1 \leq i < k$$$.

Input format:
Each test contains multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — the number of test cases. The following lines contain the description of each test case.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$2 \leq k \leq n \leq 1000$$$).

Then $$$n$$$ lines follow. The $$$i$$$-th line contains a binary string $$$s_i$$$ of length $$$n$$$. The $$$j$$$-th character of $$$s_i$$$ is 1 if you can delete cell $$$(i, j)$$$, and 0 otherwise.

It's guaranteed that the sum of $$$n^2$$$ over all test cases does not exceed $$$10^6$$$.

Output format:
For each test case, if there is no way to delete exactly $$$(n-k+1)^2$$$ cells to meet the condition, output "NO" (without quotes).

Otherwise, output "YES" (without quotes). Then, output $$$n$$$ lines. The $$$i$$$-th line should contain a binary string $$$t_i$$$ of length $$$n$$$. The $$$j$$$-th character of $$$t_i$$$ is 0 if cell $$$(i, j)$$$ is deleted, and 1 otherwise.

If there are multiple solutions, you can output any of them.

You can output "YES" and "NO" in any case (for example, strings "yEs", "yes" and "Yes" will be recognized as a positive response).

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
For the first test case, you only have to delete cell $$$(1, 1)$$$.

For the second test case, you could choose to delete cells $$$(1,1)$$$, $$$(1,2)$$$, $$$(4,3)$$$ and $$$(4,4)$$$.

For the third test case, it is no solution because the cells in the diagonal will always form a strictly increasing sequence of length $$$5$$$.

Example input:
4
2 2
10
01
4 3
1110
0101
1010
0111
5 5
01111
10111
11011
11101
11110
5 2
10000
01111
01111
01111
01111

Example output:
YES
01
11
YES
0011
1111
1111
1100
NO
YES
01111
11000
10000
10000
10000

Editorial:
Consider increasing diagonals (sets of cells $$$(x, y)$$$ for which $$$x - y = c$$$ for some fixed $$$c$$$). Clearly, from the diagonal of length $$$t$$$, we have to delete at least $$$\max(0, t - (k-1))$$$ cells. There are $$$2$$$ diagonals of length $$$i$$$ for each $$$i$$$ from $$$1$$$ to $$$n-1$$$ and one diagonal of length $$$n$$$, so we have to delete at least $$$2 + 4 + \ldots + 2(n-k) + (n-k+1) = (n-k+1)^2$$$ cells from them in total. This means that we will delete precisely $$$\max(0, t - (k-1))$$$ cells from the diagonal of length $$$t$$$.
Now, consider two adjacent diagonals of lengths $$$t-1$$$ and $$$t$$$ for some $$$t \ge k$$$. Let's call diagonal of length $$$t$$$ large, and of $$$t-1$$$ small. Let's enumerate cells of large diagonal from $$$1$$$ to $$$t$$$, and of small from $$$1$$$ to $$$t-1$$$. We have to delete precisely $$$t-k+1$$$ cells from large diagonal, and $$$t-k$$$ from small. Suppose that the cells deleted from the large diagonal have indexes $$$1 \le x_1<x_2<\ldots<x_{t-k+1} \le t$$$.
For some $$$1 \le j \le t-k$$$, consider the path, containing cells from $$$1$$$-st to $$$(x_j-1)$$$-st in the large diagonal, from $$$x_j$$$-th to $$$(x_{j+1}-1)$$$-st in the small diagonal, and from $$$(x_{j+1}+1)$$$-st to $$$t$$$-th in the large diagonal. Note that this is an increasing sequence of cells of length $$$t-1$$$, so we have to delete at least $$$t-k$$$ cells from it. We deleted precisely $$$t-k-2$$$ cells from it in the large diagonal, so we have to delete at least one cell in the small diagonal in the range $$$[x_j, x_{j+1}-1]$$$.
Note that the ranges $$$[x_j, x_{j+1}-1]$$$ for $$$1 \le j \le t-k$$$ don't intersect, and there are $$$t-k$$$ of them. So, we have to delete precisely one cell from each such range and not delete any cell outside of $$$[x_1, x_{t-k+1}-1]$$$.
Surprisingly, these criteria are sufficient (meaning that for every two adjacent diagonals, the cells in the smaller one are deleted in these ranges determined from the cells deleted in the larger one). Let's first show how to solve the problem based on this and then how to prove that this is sufficient.
If these criteria are indeed sufficient, then let's construct the set of deleted cells one by one (if it exists).
• How do we choose the first deleted cell on the main diagonal? Just choose the first cell which you can delete.
• How do we choose the first deleted cell on the diagonals adjacent to the main diagonal? Just choose the first cell which you can delete that goes after the deleted cell in the main diagonal.
• How do we choose the second deleted cell on the main diagonal and the first deleted cells on the diagonals of length $$$n-2$$$? Again, just choose the first cell that you are allowed to delete which does not violate the conditions.
• (and so on)
You can simulate this greedy in just $$$O(n^2)$$$  — just keep for each diagonal the last deleted cell. If at any point there were no allowed cells, then answer is NO, otherwise, we found the construction.
How to prove that this is sufficient? Let's prove the following statement.
Lemma: In each cell $$$(x, y)$$$, write the number of non-deleted cells in the diagonal of $$$(x, y)$$$, up to the cell $$$(x, y)$$$. Denote this number by $$$a_{x, y}$$$. Then $$$a_{x-1, y} \le a_{x, y}$$$ for any $$$1 \le x \le n-1$$$, $$$1 \le y \le n$$$, and $$$a_{x, y-1} \le a_{x, y}$$$ for any $$$1 \le x \le n$$$, $$$1 \le y \le n-1$$$ (in other words, $$$a$$$ is nondecreasing by rows and columns).
Proof: Almost trivial from our constraints. Let's show that $$$a_{x-1, y} \le a_{x, y}$$$, for example. If cell $$$(x-1, y)$$$ is on the main diagonal or lower, then cell $$$(x-1, y)$$$ is on a larger diagonal than $$$(x, y)$$$. We deleted $$$y - a_{x, y}$$$ cells in the diagonal of $$$(x, y)$$$ up to this cell. Therefore, the $$$(y - a_{x, y})$$$-th deleted cell in the larger diagonal has to have $$$y$$$ coordinate at most $$$y$$$ as well, so we deleted at least $$$y - a_{x, y}$$$ cells in the diagonal of $$$(x-1, y)$$$ up to that cell, and there are at most $$$a_{x, y}$$$ not deleted cells there. The similar argument goes for the case when $$$(x-1, y)$$$ is above the main diagonal.
With this lemma, suppose that there is an increasing sequence of not deleted cells $$$(x_1, y_1), (x_2, y_2), \ldots, (x_k, y_k)$$$ (with $$$x_i < x_{i+1}, y_i<y_{i+1}$$$). Then it's easy to show that $$$a_{x_i, y_i}<a_{x_{i+1}, y_{i+1}}$$$. Indeed, $$$a_{x_i, y_i}\le a_{x_{i+1}-1, y_{i+1}-1} = a_{x_{i+1}, y_{i+1}} - 1$$$. But then we would get $$$a_{x_k, y_k} \ge k$$$, which obviously doesn't hold (there are at most $$$k-1$$$ not deleted cells in each diagonal by our construction).
Bonus: It's possible to show that the answer is NO if and only if there is an increasing sequence of $$$k$$$ cells, each of which we aren't allowed to delete. Proof is left to the reader as an exercise.