saksham2005mittal's blog

Codeforces Round 1120 (Div. 2) — B — Min Matrices
By saksham2005mittal, history, 2 hours ago, In English

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.

  • Vote: I like it
  • -5
  • Vote: I do not like it

»
2 hours ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by saksham2005mittal (previous revision, new revision, compare).

→ Reply
»
119 minutes ago, hide # |
← Rev. 5  
Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    103 minutes ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    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!

    → Reply
    • »
      »
      »
      20 minutes ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      I actually didn't have any L shaped patterns, it was all just a single bar down the left and the whole diagonal.

      → Reply