Submit | All submissions | Best solutions | Back to list |
NPC2014H - Arithmetic Rectangle |
There is a matrix with size N x M where each cell contains an integer. An arithmetic rectangle is a rectangle inside the matrix so that each row and column is an arithmetic progression. An arithmetic progression is a sequence so that each number minus the number before it is the same. Given a matrix, find the largest arithmetic rectangle, which is the arithmetic rectangle containing the most number of cells. For example, the largest arithmetic rectangles of the matrix below consists of 9 cells:
Input
First line of input is T, the number of test cases. Each test case starts with N and M. The next N lines each containing M integers Aij representing the value of each cell of the matrix. Each input file will not exceed 20 MB in size.
Output
For each test case output the number of cells in the largest arithmetic rectangle in the matrix.
Sample Input
2 4 4 5 3 5 7 2 4 4 4 3 5 3 1 6 3 2 4 2 3 0 1 2 1 2 3
Sample Output
9 6
Constraint
- 1 ≤ T ≤ 10000
- 1 ≤ N, M ≤ 3000
- 0 ≤ Aij ≤ 1000000000
Input file is huge, is faster I/O (scanf for C)
Added by: | Andy |
Date: | 2014-10-21 |
Time limit: | 1s-1.5s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | NPC Schematics 2014 |
hide comments
2014-11-04 12:51:34 Infinity
@Monyet , Yes We can easily solve this in O(N^2), instead of dp with segmented tree , try using the concept from "Largest area of a rectangle in histogram" :D |
|
2014-10-30 17:42:33 Andy
@monyet I don't know what the intended solution is, but glad you liked the problem! |
|
2014-10-30 09:24:18 Monyet
What is the expected complexity for this problem ? My solution is O(N^2 log N). It uses DP + segment tree. Is there O(N^2) solution? @Andy : Soal NPC nya mantap2 kak ! |
|
2014-10-25 18:34:08 Andy
considering 3000x3000 int is already around 35MB, I don't think so |
|
2014-10-25 15:23:07 Infinity
@Jaco/Andy: is this possible under 10 M storage ?-i challenge- Last edit: 2014-10-25 15:24:02 |