# 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:

- 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:

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

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:

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

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