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 \lt 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 \gt 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.
Полный текст и комментарии »
