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

AndyZhang68 commented on May 16, 2025, 2:56 a.m.

Another way (which also passes in Python) is to essentially build a 2d prefix sum array and then for each empty cell (or just check empty cells to the left of a wall to optimize) is to binary search to find the first cell to the left, and that gives a length of a potential table. Then, binary search up and down to find how wide the table can be expanded on both sides. The binary searching can use the 2d prefix sum array to handle range queries, resulting in a $O(n^2 \log n)$ ~O(n^2 \log n)~ time complexity. The constant factor can be lowered by reducing the amount of empty cells you choose to process.

1

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

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.)