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


  • 0
    Ivan_Li  commented on Oct. 20, 2023, 8:07 p.m. edited

    There is also an \mathcal{O}(N^2) solution to this problem by reducing the problem to largest rectangle in a histogram, and then solving with a monotonic stack. The only modification you need is to use the formula for perimeter instead of area. Example: https://dmoj.ca/src/5742708

    (You need this method to pass with Python.)