There is a determined solution - the one i've got AC with. Idea from this post https://codeforces.com/blog/entry/92092 can be applied to 2D case.

Edited by author 20.04.2023 17:25

by the way, use 123 and 1789 in hashing will pass.

why don't you share your strong tests with us then?

Sorry. I can't.

Me neither.

Chill out

Could you be more specific?
Because I try:
1. Point (row, col) closest to point (1,1) first (distance formula).
2. Row closest to row 1 first.
3. Other variations

And I still get WA7.

Let's call a number k "good" if there are two same squares with side length k in the matrix. I claim that if k is good, then k - 1 is good. Indeed, let's look at any pair of same squares with side length k. Now, let's take the left-upper square with side k - 1 in each of them. Note that they will be equal, but still won't be in the same place in the matrix, so they will be a good pair of squares with side length k - 1. We've just proved that if K is the side length of the optimal pair of squares, then k = 1, 2, ... , K are all good, while k = K + 1, K + 2, ... , min(n, m) are all bad. Hence, we can do binary search to find K. The only thing left is how to check for a given k whether there are two equal squares with side length k or not. This part can be done by using hashing.

You have a collisions with hash. (I've got this problem also because second number x was to small and close to first one).

Why you have used binary search? How we can say that the sq. matrix 2x2 has less value than 3x3. and 3x3 has less than 4x4. how can we justify?

Nice!  I just checked the discussion before writing hash solution...

Probably the problem can be solved using two-dimensional hashing Rabin-Carp algorithm.

You can change map/set into unordered_map/set get faster, reduce time O(lg n) O(∩_∩)O

Edited by author 07.09.2016 18:47

if you are a chinese ,
you can read the article —— Hash在信息学竞赛中的一类应用

you should output "0".

yes. you should output "0" iff no 1x1 squares match.

Only thing you need is z = O(1).

Edited by author 15.02.2007 22:43

Pasha, if you accept this ...
help me to do this too!
   Good Luck!

     Chobit'my jiji, chobit'my!!!

I have f..ed this problem!
I did this problem the same as you did.
my Modulo in hash table = 999983.