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)$ $s u m (r o w, c o l u m n)$ . After calculating this, the expression $sum(row, s_2) - sum(row, s_1-1)$ $s u m (r o w, s_{2}) - s u m (r o w, 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)$ $O (N^{2})$ .

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

Comments

1

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

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