Editorial for COCI '13 Contest 2 #2 Misa


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.

We check if each seating place inside the church is available or not. If it is available, we check for the number of its non-available neighbours, to find out whether Mirko will sit there. If it is not available, yet again we need the number of its non-available neighbours in order to count them in the total number of handshakes.

How to check an item's (row, column) 8 neighbours simply? Its neighbours are the following:

\displaystyle \begin{align*}
&(row-1, column-1) \\
&(row-1, column) \\
&(row-1, column+1) \\
&(row, column-1) \\
&(row, column+1) \\
&(row+1, column-1) \\
&(row+1, column) \\
&(row+1, column+1)
\end{align*}

For each item, we must check whether it is a part of our seating matrix (that is, if its coordinates are greater than zero and not greater than R or S) and whether it is already occupied. Manually checking each condition can be time-consuming, so we use two arrays to help us:

  • array move\_by\_row = (-1, -1, -1, 0, 0, 1, 1, 1),
  • array move\_by\_column = (-1, 0, 1, -1, 1, -1, 0, 1).

Using a for loop, we will iterate from 1 to 8 and calculate for each i:

  • row\_neighbours = row + move\_by\_row[i]
  • column\_neighbours = column + move\_by\_column[i]

If you think about it, you will see that this way we iterate through all 8 of our current element's neighbours. Inside the for loop we still have to check the aforementioned conditions.

The total number of handshakes during the Mass, without Mirko, is equal to the sum of calculated handshakes of all neighbouring non-available elements divided by two, because we counted each handshake twice. We still have to add the number of Mirko's handshakes, which is represented by the maximum number of neighbouring items of the current item.


Comments

There are no comments at the moment.