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.
Auto comment: topic has been updated by saksham2005mittal (previous revision, new revision, compare).
Here's what I did:
Min set A size: place the smallest n values on the longest diagonal.
Max set A size: populate the left most column with the first n smallest numbers, and place the next n — 1 smallest numbers along the long diagonal (diagonal means from (1,1) — (n, n)).
Everything in between: place 1 at position [0][0]. Then you place the next n — k smallest numbers directly below the 1 -- along the left most column, finally place the next n — 1 smallest numbers along the main diagonal (diagonal means from (1,1) -> (n, n)).
Fill up the rest: The rest of the numbers can go wherever you want, in any order.
Pretty neat little constructive problem: https://codeforces.me/contest/2263/submission/390437547
Yeah, your's is far better... tbh I used up all my brain cells in that proof, I had very little time left to actually code it out. I did notice the "L" shape patterns when I was thinking over this during the contest, but yeah during implementation I could've done better.
Thanks for reading!
I actually didn't have any L shaped patterns, it was all just a single bar down the left and the whole diagonal.