ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1486. Equal Squares

binary search
Posted by Anwar 17 Sep 2018 19:02
Why use a binary search. How can we say that the value of the hash of 4x4 > 3x3 > 2x2 > 1x1? I don`t understand why to use binary search.
plz, help me...
Re: binary search
Posted by Alikhan Zimanov 5 Jun 2020 16:06
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.