Misha and Paintings
Contest: Codeforces Round 815 (Div. 2)
Difficulty rating: 2700
Tags: constructive algorithms, data structures, greedy, implementation, math

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:

1. 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$$$),
2. choose an integer $$$k$$$, where $$$1 \leq k \leq n^2$$$,
3. replace all integers in the submatrix with $$$k$$$.

Please find the minimum number of operations that Misha needs to achieve his goal.

Input format:
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 format:
Output one integer — the minimum number of operations required.

Constraints:
Time limit: 3.5 s
Memory limit: 256.0 MB

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:

111112341

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:

111111112

Example input:
3 4
1 1 1
1 1 2
3 4 5

Example output:
1

Example input:
3 2
2 1 3
2 1 1
3 1 2

Example output:
2

Editorial:
If $$$k$$$ is greater than the number of different numbers in the matrix, then the answer is $$$k$$$ minus the number of different elements.
Otherwise the answer does not exceed 2.
Let's proof that: choose the maximum square (let its side be equal to $$$L$$$), containing the top left corner of the matrix, such as recolouring it to some new colour makes the number of different colours in the table at least $$$k$$$.
• If the number of different colours after recolouring is greater than $$$k$$$, then choose a square with bottom right corner in $$$(L + 1, L + 1)$$$, such as recolouring it makes the number of different colours at least $$$k$$$. If we got exactly $$$k$$$ colours then we are done. Otherwise let's extend the square by one. We got $$$k$$$ or $$$k - 1$$$ different colours. This way, by choosing the correct colour of the square we can get exactly $$$k$$$ colours
• Otherwise we are done.
It remains to learn how to check whether the answer is equal to 1. We will iterate over length of the side of the square of the answer. Now we need $$$O(n^2)$$$ to check whether the required square with such a side exists. To do this, we calculate for each square in the table with such a side length (there are $$$n^2$$$ such squares), how many numbers this square completely covers (all appeareances of this numbers are in thsi square). To do this, let's iterate over the number $$$c$$$. Having considered its occurrences, it is easy to understand that the upper left corners of all squares with our side length, covering all cells with the number $$$c$$$, lie in some subrectangle of the table, so you can simply add 1 on this subrectangle using offline prefix sums. Having processed all the numbers in this way, we can count for each square how many numbers it covers completely, and therefore check whether it fits the requirements.
Complexity: $$$O(n^3)$$$