Editorial for COCI '21 Contest 5 #2 Dijamant
Submitting an official solution before solving the problem yourself is a bannable offence.
Notice that if somewhere in the table there is a diamond shape whose edge is made out of #
, then its interior is also a diamond shape, but its edge is from .
instead of #
. Therefore, it is enough to iterate over the table and using BFS or DFS, find the maximal connected regions made from .
and for each such region, check if it has a diamond shape.
Let's now look at all cells for which , for some fixed value of . It's easy to see that those cells will form a diagonal in the table going in the direction from bottom-left to top-right. Also, smaller values of correspond to diagonals closer to the top-left corner of the table, while larger values of correspond to diagonals closer to the bottom-right corner of the table. In a similar way, the set of cells for which forms a diagonal, but in the other direction. This means that if we are given fixed numbers , , and such that and , then the set of all cells for which and actually forms a tilted rectangle. In case , it is actually a tilted square, i.e. a diamond.
Therefore, to check if some region is a diamond or not, we keep track of the following: the number of visited cells (cnt
), and the minimum and maximum diagonal in both directions (, , , ). What remains is to check whether and to see if the number of visited cells matches the number of cells that should be in the diamond of this size (). In doing so, we need to calculate the number of .
in a diamond of size , which turns out to be .
Comments