APGRID Editorial

editorial
, ,
1

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Daanish Mahajan
Tester: Abhinav Sharma, Nishank Suresh
Editorialist: Pratiyush Mishra

DIFFICULTY:

1562

PREREQUISITES:

None

PROBLEM:

Construct an N \times M matrix with entries having positive integers such that:

  • If M \gt 1, i^{th} row is strictly increasing from left to right with a fixed common difference d_i for all 1\le i \le N.
  • If N \gt 1, j^{th} column is strictly increasing from top to bottom with a fixed common difference c_j for all 1\le j \le M.
  • All the common differences should be distinct.
  • In the case of multiple answers, find an arrangement that minimizes the maximum element of the matrix.

EXPLANATION:

In order to keep the maximum element minimum we would start with 1, as the first element of the 2-D array. Now there can be two cases:

  • n \leq m: Here since m is greater so it implies that the length of rows would be longer as compared to length of columns so to keep the maximum element minimum we would assign smaller common differences for rows as compared to columns. So in this case:
d_i = i ,\; 1 \leq i \leq n \\ c_j = m + j,\; 1 \leq j \leq m
  • n > m: Here since n is greater so it implies that the length of columns would be longer so to keep maximum element minimum we would assign smaller common differences for columns as compared to rows. So in this case:
d_i = m + i ,\; 1 \leq i \leq n \\ c_j = j,\; 1 \leq j \leq m

Now any term A_{ij}(i, j as 0 based index) can be calculated as:

For\; n \leq m : 1 + (n + 1)\times i + j \times (i + 1) \;\;...(i) \\ For\; n > m : 1 + i + j \times (m + 1 + i) \;\;...(ii)

Proof for selection of common differences:
Let’s take the case of n \leq m, then the maximum term would be A_{n-1m-1}. Now consider values of A_{n-1m-1}, for both above cases:

A'_{n-1m-1} = 1 + (n+1) \times (n-1) + (m-1) \times n,\; as \;per\; (i) \\ A''_{n-1m-1} = 1 + (n-1) + (m-1) \times(m+n), as\;per\;(ii)

Taking L as A'_{n-1m-1} - A''_{n-1m-1}, we get:

L = (n-m)(n+m-1)

Since n \leq m, therefore L \leq 0, so A'_{n-1m-1} \leq A''_{n-1m-1}.

Hence the maximum term is less in case we go by (i). Similarly we can prove for m > n.

TIME COMPLEXITY:

O(NM), for each test case.

SOLUTION:

Editorialist’s Solution
Setter’s Solution
Tester1’s Solution
Tester2’s Solution

3

Your proof is lacking. You just came up with 2 arrangements and PROVING the optimal of THOSE 2. However, you need to prove the OPTIMALITY against all possible arrangements.

1 Like
4

Glad I’m not the only one who thought that. Still waiting then.