Codeforces Round 815 (Div. 2) |
---|
Finished |
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:
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.
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
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 |
Name |
---|