Codeforces Round 1120 (Div. 2) — B — Min Matrices

#	User	Rating
1	jiangly	3810
2	Kevin114514	3655
3	Benq	3650
4	maroonrk	3427
5	strapple	3413
6	Um_nik	3387
7	heuristica	3322
8	tourist	3301
9	turmax	3297
10	squareOf105	3262

#	User	Contrib.
1	Qingyu	157
2	maspy	150
3	nik_exists	149
4	Um_nik	145
5	Errichto	139
6	adamant	136
7	maroonrk	134
8	AmShZ	133
8	BledDest	133
10	DNR	130

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.