MINGCD_1 - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: kryptonix171
Tester: mexomerf
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

Find any N\times M grid with minimum sum containing integers between 2 and 10^9, such that every row and every column has GCD 1.

EXPLANATION:

Our aim is to minimize the sum, and the smallest number we can use is 2.
Clearly, this means that the absolute best scenario is when every element of the grid is 2.
However, this doesn’t fulfill the condition on GCDs of each row/column being 1.

The next smallest number we can use is 3, and conveniently, \gcd(2, 3) = 1.
So, if we simply place a single occurrence of 3 in each row and each column, and leave everything else at 2, we’ll satisfy the GCD requirement.
Of course, we do want to minimize the number of 3's, which means ideally, each 3 we place should account for both a row and a column.

One simple way of doing that is to place them along the main diagonal; and then fill up any remaining rows/columns somehow.
For example, when N \leq M, it’ll be something like

\begin{bmatrix} 3 \\ \ & 3 \\ & & 3 \\ & & & 3 \\ & & & & \ddots\\ & & & & & 3 & 3 & 3 & \ldots & 3 \end{bmatrix}

with every other cell filled with 2.

In general, we’ll place exactly \max(N, M) occurrences of 3, which is clearly optimal.

TIME COMPLEXITY:

\mathcal{O}(N\cdot M) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n, m = map(int, input().split())
    a = [ [2]*m for _ in range(n)]
    for i in range(max(n, m)):
        r, c = min(n-1, i), min(m-1, i)
        a[r][c] = 3
    for row in a: print(*row)
1 Like
2

this problem is rated ~2500 lol

1 Like