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:

5,3,5,7/2,4,4,4/3,5,3,1/6,3,2,4

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
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.