I am stuck on problem to count total number of such squares whose boundary consists of ones only in binary matrix.Please help. Problem Link:
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
I am stuck on problem to count total number of such squares whose boundary consists of ones only in binary matrix.Please help. Problem Link:
Name |
---|
link of video solution of similar kind of question
On a surface, the idea is to work on each diagonal seperately as each diagonal will have the top leftmost and bottom rightmost point of a square. Now for each element,if it's the top leftmost element, then the bottom-rightmost element will lie in some range,Same thing holds for bottom rightmost elements. It reduces the problem to finding total number of relevant intersections of ranges in each diagonal which can be done in nlogn for each diagonal.