The problem at hand can be expressed as:↵
$$f(A)=\{x \mid x \in A, x=\text{min(row) or min(col)} \}$$↵
↵
$$\forall \; x \in [1, n^2] \; \cap \; \mathbb{Z}, \mid x \in A \; \& \; \lvert f(A) \rvert=k \implies \begin{cases} \nexists \; A \;, \lvert f(A) \rvert=k \to -1 \\ \exists \; A \;, \lvert f(A) \rvert=k \to A \end{cases}$$↵
↵
On inspection of various 3x3 matrix arrangements, we have the following:↵
↵
**Observation 1:** To minimize `k` the diagonal elements must contain the least elements (row). From this we can conclude that:↵
↵
$$\forall \; k <n, \; \nexists \; A, \; \lvert f(A) \rvert = k \implies -1$$↵
↵
**Observation 2:** To maximize `k` the row minimum elements must be in one line. From this we can conclude that:↵
↵
$$\forall \; k > 2n-1, \; \nexists \; A, \; \lvert f(A) \rvert=k \implies -1$$↵
↵
From the above two observations we can conclude that:↵
↵
$$\exists \; A, \; \lvert f(A) \rvert=k \implies k \in [n, 2n - 1] \; \cap \; \mathbb{Z}$$↵
↵
Thus, considering the above observations to be true, we now have a valid range of `k`, outside of which we can directly conclude the final result to be `-1`.↵
↵
Let in the test case, given `k` be $k_d$. Then for some $t$,↵
↵
$$k_d=2n-1-t \implies t=(2n-1)-k_d$$↵
↵
$(n-t)$ minimum row elements must be in the same column for $\lvert f(A) \rvert = k_d$. So,↵
↵
$$(n-t)\mid_{t=(2n-1)-k_d}=k_d-n+1 \implies \boxed{(k_d-n+1), \; 1 \le k_d \le n}$$↵
↵
Therefore for an intermediate `k` i.e. between observations 1 and 2, first $(k_d - n + 1)$ elements in range $[1, n] \; \cap \; \mathbb{Z}$ must be in same column in `A`.↵
↵
## Conclusion↵
↵
$$\forall \; x \in [1, n^2] \; \cap \; \mathbb{Z}, \mid x \in A \; \& \; \lvert f(A) \rvert=k \implies \begin{cases} \nexists \; A \;, \lvert f(A) \rvert=k \to -1 \\ \exists \; A \;, \lvert f(A) \rvert=k \to A \end{cases}$$↵
↵
$$\exists \; A, \; \lvert f(A) \rvert=k \; \text{iff} \; k \in [n, 2n-1] \; \cap \; \mathbb{Z}, \; k_d: \text{desired } k$$↵
↵
subject to↵
↵
$$\forall \; x \in [1, k_d - n + 1] \; \cap \; \mathbb{Z} \; \mid \; x \in C_\gamma \; \text{where} \; C_\gamma \in \text{cols}(A) \; \& \; 1 \le k_d \le n$$↵
↵
The implementation can be found [here](https://codeforces.me/contest/2263/submission/390480436).
$$f(A)=\{x \mid x \in A, x=\text{min(row) or min(col)} \}$$↵
↵
$$\forall \; x \in [1, n^2] \; \cap \; \mathbb{Z}, \mid x \in A \; \& \; \lvert f(A) \rvert=k \implies \begin{cases} \nexists \; A \;, \lvert f(A) \rvert=k \to -1 \\ \exists \; A \;, \lvert f(A) \rvert=k \to A \end{cases}$$↵
↵
On inspection of various 3x3 matrix arrangements, we have the following:↵
↵
**Observation 1:** To minimize `k` the diagonal elements must contain the least elements (row). From this we can conclude that:↵
↵
$$\forall \; k <n, \; \nexists \; A, \; \lvert f(A) \rvert = k \implies -1$$↵
↵
**Observation 2:** To maximize `k` the row minimum elements must be in one line. From this we can conclude that:↵
↵
$$\forall \; k > 2n-1, \; \nexists \; A, \; \lvert f(A) \rvert=k \implies -1$$↵
↵
From the above two observations we can conclude that:↵
↵
$$\exists \; A, \; \lvert f(A) \rvert=k \implies k \in [n, 2n - 1] \; \cap \; \mathbb{Z}$$↵
↵
Thus, considering the above observations to be true, we now have a valid range of `k`, outside of which we can directly conclude the final result to be `-1`.↵
↵
Let in the test case, given `k` be $k_d$. Then for some $t$,↵
↵
$$k_d=2n-1-t \implies t=(2n-1)-k_d$$↵
↵
$(n-t)$ minimum row elements must be in the same column for $\lvert f(A) \rvert = k_d$. So,↵
↵
$$(n-t)\mid_{t=(2n-1)-k_d}=k_d-n+1 \implies \boxed{(k_d-n+1), \; 1 \le k_d \le n}$$↵
↵
Therefore for an intermediate `k` i.e. between observations 1 and 2, first $(k_d - n + 1)$ elements in range $[1, n] \; \cap \; \mathbb{Z}$ must be in same column in `A`.↵
↵
## Conclusion↵
↵
$$\forall \; x \in [1, n^2] \; \cap \; \mathbb{Z}, \mid x \in A \; \& \; \lvert f(A) \rvert=k \implies \begin{cases} \nexists \; A \;, \lvert f(A) \rvert=k \to -1 \\ \exists \; A \;, \lvert f(A) \rvert=k \to A \end{cases}$$↵
↵
$$\exists \; A, \; \lvert f(A) \rvert=k \; \text{iff} \; k \in [n, 2n-1] \; \cap \; \mathbb{Z}, \; k_d: \text{desired } k$$↵
↵
subject to↵
↵
$$\forall \; x \in [1, k_d - n + 1] \; \cap \; \mathbb{Z} \; \mid \; x \in C_\gamma \; \text{where} \; C_\gamma \in \text{cols}(A) \; \& \; 1 \le k_d \le n$$↵
↵
The implementation can be found [here](https://codeforces.me/contest/2263/submission/390480436).
