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$ ~s_1~ and end in column $s_2$ ~s_2~. For the table to span a certain row, all squares between $s_1$ ~s_1~ and $s_2$ ~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$ ~s_1~ and $s_2$ ~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)$ ~sum(row, column)~. After calculating this, the expression $sum(row, s_2) - sum(row, s_1-1)$ ~sum(row, s_2) - sum(row, s_1-1)~ tells us how many squares between $s_1$ ~s_1~ and $s_2$ ~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$ ~s_1~ and $s_2$ ~s_2~, giving the largest solution for the assumed columns $s_1$ ~s_1~ and $s_2$ ~s_2~. Exploring all possibilities for $s_1$ ~s_1~ and $s_2$ ~s_2~ we choose the one that gives the maximum perimeter.

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

Time complexity: $\mathcal O(N^3)$ ~\mathcal O(N^3)~

Comments

0

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

There is also an $\mathcal{O}(N^2)$ ~\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.)