[Solution] Subrectangle Guess solution codeforces

Subrectangle Guess solution codeforces – Michael and Joe are playing a game. The game is played on a grid with 𝑛n rows and 𝑚m columns, filled with distinct integers. We denote the square on the 𝑖i-th (1𝑖𝑛1≤i≤n) row and 𝑗j-th (1𝑗𝑚1≤j≤m) column by (𝑖,𝑗)(i,j) and the number there by 𝑎𝑖𝑗aij.

Table of Contents

[Solution] Subrectangle Guess solution codeforces

Michael starts by saying two numbers h (1𝑛1≤h≤n) and 𝑤w (1𝑤𝑚1≤w≤m). Then Joe picks any ×𝑤h×w subrectangle of the board (without Michael seeing).

Formally, an ×𝑤h×w subrectangle starts at some square (𝑎,𝑏)(a,b) where 1𝑎𝑛+11≤a≤n−h+1 and 1𝑏𝑚𝑤+11≤b≤m−w+1. It contains all squares (𝑖,𝑗)(i,j) for 𝑎𝑖𝑎+1a≤i≤a+h−1 and 𝑏𝑗𝑏+𝑤1b≤j≤b+w−1.

Subrectangle Guess solution codeforcesPossible move by Joe if Michael says 3×23×2 (with maximum of 1515).
Finally, Michael has to guess the maximum number in the subrectangle. He wins if he gets it right.

Because Michael doesn’t like big numbers, he wants the area of the chosen subrectangle (that is, 𝑤h⋅w), to be as small as possible, while still ensuring that he wins, not depending on Joe’s choice. Help Michael out by finding this minimum possible area.

[Solution] Subrectangle Guess solution codeforces

It can be shown that Michael can always choose ,𝑤h,w for which he can ensure that he wins.

Input

Each test contains multiple test cases. The first line contains the number of test cases 𝑡t (1𝑡201≤t≤20). Description of the test cases follows.

The first line of each test case contains two integers 𝑛n and 𝑚m (1𝑛,𝑚401≤n,m≤40)  — the size of the grid.

Each of the following 𝑛n lines contains 𝑚m integers. The 𝑗j-th integer on the 𝑖i-th line is 𝑎𝑖𝑗aij (109𝑎𝑖𝑗109−109≤aij≤109)  — the element in the cell (𝑖,𝑗)(i,j).

It is guaranteed that all the numbers are distinct (that is, if 𝑎𝑖1𝑗1=𝑎𝑖2𝑗2ai1j1=ai2j2, then 𝑖1=𝑖2,𝑗1=𝑗2i1=i2,j1=j2).

Output

For each test case print a single positive integer  — the minimum possible area the subrectangle can have while still ensuring that Michael can guarantee the victory.

[Solution] Subrectangle Guess solution codeforces

Example
input

Copy
3
1 1
3
4 4
2 12 6 10
3 15 16 4
1 13 8 11
14 7 9 5
2 3
-7 5 2
0 8 -3

[Solution] Subrectangle Guess solution codeforces

output

Copy
1
9
4
Note

In the first test case, the grid is 1×11×1, so the only possible choice for ,𝑤h,w is =1,𝑤=1h=1,w=1, giving an area of 𝑤=1h⋅w=1.

The grid from the second test case is drawn in the statement. It can be shown that with =3,𝑤=3h=3,w=3 Michael can guarantee the victory and that any choice with 𝑤8h⋅w≤8 doesn’t.

For Solution

Click Here

Leave a Comment