Editorial for COCI '06 Contest 2 #5 Stol


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.

Suppose one dimension of the table is fixed. For example, let the table start in column s_1 and end in column s_2. For the table to span a certain row, all squares between s_1 and s_2 (inclusive) in that row must be free.

For each row we can determine if there are any blocked squares between columns s_1 and s_2 in constant time: we preprocess the apartment and calculate the number of blocked squares left of each square. Call this number sum(row, column). After calculating this, the expression sum(row, s_2) - sum(row, s_1-1) tells us how many squares between s_1 and s_2 are blocked (if this number is zero, then the table can be placed in that row).

A single pass finds the largest consecutive number of rows that don't have walls between s_1 and s_2, giving the largest solution for the assumed columns s_1 and s_2. Exploring all possibilities for s_1 and s_2 we choose the one that gives the maximum perimeter.

The number of possibilities is \mathcal O(N^2).

Time complexity: \mathcal O(N^3)


Comments

There are no comments at the moment.