MXSBMTRX - Largest Increasing Sub-Matrix
Mosa loves all sorts of properties of matrices. One day his coach Fegla asked him to draw a matrix with size N × M and insert random numbers in each cell, then he asked him to find the largest increasing sub-matrix.
It's defined as a matrix that each cell in the position (i, j) is greater than the cells in positions:
(i - 1, j), (i, j - 1) and (i - 1, j - 1).
Help Mosa to find the size of the largest increasing sub-matrix.
Input
t - the number of test cases, then t test cases follows. [t <= 50]
Each test case contains two integers N and M indicating the matrix dimensions [1 <= N * M <= 105].
Each of the next N lines contains M integers, separated by a space, describing the elements of the matrix.
Element Xi,j of the matrix is the jth integer of the ith line in the input [-109 <= Xi,j <= 109].
Output
For each test case in the input your program must print on single line, containing the solution of the problem.
Example
Input: 2 2 3
2 2 2
2 2 2 3 3
1 2 5
4 6 7
10 8 3 Output: 1
6
hide comments
Oleg:
2023-10-17 02:38:55
See also https://www.spoj.com/problems/NPC2014H/ |
|
eagle93:
2014-05-28 17:46:07
@Aditya Deepak: Yes, n could be 10^5, m = 1 and vice versa.
|
|
adijimmy:
2014-05-23 11:42:56
what are the constraints for the value of n and m ?? admin please reply as its too vague as n*m<=10**5 as in this case maximum and minimum value of n,m can be 10**5 and 1 and if this is so we cant allocate so much memory :( |
|
eagle93:
2014-03-21 14:04:04
@Apoorv Jindal:
|
|
Apoorv Jindal:
2014-03-06 09:51:38
The problem statement is ambiguous! What will be the output for:
|
|
Jacob Plachta:
2014-02-17 07:28:35
Alright, thanks! |
|
eagle93:
2014-02-17 06:52:27
@Jacob Plachta: It's my fault!
|
|
Jacob Plachta:
2014-02-16 22:24:06
Was the data definitely uploaded correctly? I've tested my code on a large number of random cases with a brute-force checker. |
Added by: | eagle93 |
Date: | 2014-02-14 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |