Editorial for COCI '14 Contest 3 #3 Silueta


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Firstly, we will describe a naive approach. We could, for example, first draw the painted image. In other words, fill the skyscrapers' area with #. After filling that out, the image from the first example from the task would look like this:

........####
####....####
####..######
####..######
####..######
************

Now we are left with whiting out the interior of the skyscrapers. Notice that the character # becomes . only if none of the surrounding characters (in all 8 directions) is .. By implementing this algorithm, we get the wanted image.

The perimeter can be calculated from the given image by carefully counting the characters #. First, let us add to the perimeter all the characters #. Notice that some of the characters # participate in building two sides, whereas some of them don't participate at all. The perimeter should be increased by the number of characters participating in two sides and decreased by the number of characters participating in none. The characters being added to the perimeter are marked with red and the ones being subtracted are marked with blue:

........####
####....#..#
#..#..###..#
#..#..#....#
#..#..#....#
************

It is clear that the characters that are being added are in fact the upper corners of the skyscrapers and are of the shape:

##      ##
#.  or  .#

whereas the characters being subtracted are the points of contact between two skyscrapers and are of the shape:

.#      #.
##  or  ##

Solutions such as this, their the complexity being \mathcal O(\text{sum_of_areas}), were enough to get 50\% of total points.

Let maxh[i] denote the maximum height of a skyscraper that stretches over the i^\text{th} column. The elements of this array can be calculated in the complexity \mathcal O(N \times (\max R_i - \min L_i)).

Calculating the perimeter comes down to linearly iterating over the array maxh where we add to the final solution the absolute difference between the adjacent elements (two vertical sides) and one for each column where maxh[i] > 0 (horizontal sides). A similar procedure is used to reconstruct the image. This implementation was sufficient for all points.


Comments


  • 0
    tanmay_raj_29  commented on April 16, 2022, 1:48 a.m.

    Why are upper corners being added twice and points of contact between two sky scrapers subtracted?