codeforces#P1720E. Misha and Paintings
Misha and Paintings
Description
Misha has a square $n \times n$ matrix, where the number in row $i$ and column $j$ is equal to $a_{i, j}$. Misha wants to modify the matrix to contain exactly $k$ distinct integers. To achieve this goal, Misha can perform the following operation zero or more times:
- choose any square submatrix of the matrix (you choose $(x_1,y_1)$, $(x_2,y_2)$, such that $x_1 \leq x_2$, $y_1 \leq y_2$, $x_2 - x_1 = y_2 - y_1$, then submatrix is a set of cells with coordinates $(x, y)$, such that $x_1 \leq x \leq x_2$, $y_1 \leq y \leq y_2$),
- choose an integer $k$, where $1 \leq k \leq n^2$,
- replace all integers in the submatrix with $k$.
Please find the minimum number of operations that Misha needs to achieve his goal.
The first input line contains two integers $n$ and $k$ ($1 \leq n \leq 500, 1 \leq k \leq n^2$) — the size of the matrix and the desired amount of distinct elements in the matrix.
Then $n$ lines follows. The $i$-th of them contains $n$ integers $a_{i, 1}, a_{i, 2}, \ldots, a_{i, n}$ ($1 \leq a_{i,j} \leq n^2$) — the elements of the $i$-th row of the matrix.
Output one integer — the minimum number of operations required.
Input
The first input line contains two integers $n$ and $k$ ($1 \leq n \leq 500, 1 \leq k \leq n^2$) — the size of the matrix and the desired amount of distinct elements in the matrix.
Then $n$ lines follows. The $i$-th of them contains $n$ integers $a_{i, 1}, a_{i, 2}, \ldots, a_{i, n}$ ($1 \leq a_{i,j} \leq n^2$) — the elements of the $i$-th row of the matrix.
Output
Output one integer — the minimum number of operations required.
Samples
3 4
1 1 1
1 1 2
3 4 5
1
3 2
2 1 3
2 1 1
3 1 2
2
3 3
1 1 1
1 1 2
2 2 2
1
3 2
1 1 1
1 2 1
2 2 2
0
Note
In the first test case the answer is $1$, because one can change the value in the bottom right corner of the matrix to $1$. The resulting matrix can be found below:
| 1 | 1 | 1 |
| 1 | 1 | 2 |
| 3 | 4 | 1 |
In the second test case the answer is $2$. First, one can change the entire matrix to contain only $1$s, and the change the value of any single cell to $2$. One of the possible resulting matrices is displayed below:
| 1 | 1 | 1 |
| 1 | 1 | 1 |
| 1 | 1 | 2 |