Largest Brick-Aligned Window
Autumn Tournament (2014)
Submission name: hole.cpp
Problem summary
An even-sized N×N wall is tiled by labelled domino bricks. Remove a maximum-area rectangular set of whole bricks, aligned with the grid and strictly separated from every outer wall boundary. Output its area and inclusive corner-cell coordinates.
Source clarification. The official editorial presents O(N³) as its full solution: https://infos.infosbg.com/files/Contests/ETI/2014/B/analyses/hole_analysis.pdf . The statement does not specify output when no internal hole exists; this implementation safely returns0 0 0 0 0 in that under-specified case, without claiming that fallback is the original judge convention.
Input
N followed by the N×N array; each domino label occurs in its two adjacent cells.
Output
Area, top row, left column, bottom row, right column, all on one line. Any maximum rectangle is allowed.
Constraints
N is even,4≤N≤1000; valid domino tiling.
Worked example
Original statement sample.
Input
6 1 1 4 4 13 14 2 3 3 5 13 14 2 6 7 5 12 12 9 6 7 10 10 15 9 8 8 11 11 15 16 16 17 17 18 18
Output
8 2 2 5 3
Solution analysis
- A rectangle removes whole dominoes exactly when none of its four boundary segments cuts through a domino. A unit boundary is blocked precisely when the two cells on its opposite sides have the same brick label. Work with internal grid lines numbered1…N−1, not with cell centres.
- Precompute horizontal unit-boundary flags and vertical prefix counts of blocked units. Fix top and bottom grid lines. Sweep possible left/right grid lines from west to east. When either horizontal boundary has a blocked unit, reset the earliest usable left boundary. Whenever a vertical line is clear between top and bottom, pair it with the earliest clear vertical line in the same horizontal-clear run.
- For fixed top and bottom, using that earliest line gives the largest width for every right boundary. Enumerate all row-line pairs and retain the best area. In the sample, cells rows2…5 and columns2…3 form an8-cell hole consisting of four complete bricks.
Why it works
No boundary of an admissible hole crosses two cells with the same label, and conversely avoiding all such crossings prevents every partial domino removal. The prefix tables test the vertical sides exactly; sweep resets ensure both horizontal sides are clear. For each right side, the earliest available left side has maximum width, so all optimum candidates are considered.
Watch out. Exclude outer grid lines0 andN. Output cell coordinates, so a top boundary at t gives top cell t+1. Validate a constructive output by area and all four boundaries rather than comparing one arbitrary optimal rectangle.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: No boundary of an admissible hole crosses two cells with the same label, and conversely
// avoiding all such crossings prevents every partial domino removal. The prefix tables test the
// vertical sides exactly; sweep resets ensure both horizontal sides are clear.
#include<iostream>
#include<vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
vector<vector<int>>wall(n,vector<int>(n));
for(auto&row:wall){
for(int&label:row){
cin>>label;
}
}
vector<vector<unsigned char>>horizontal(n,vector<unsigned char>(n));
vector<vector<int>>blocked(n+1,vector<int>(n,0));
for(int row=0;row<n;row++){
for(int cut=1;cut<n;cut++){
blocked[row+1][cut]=blocked[row][cut]+(wall[row][cut-1]==wall[row][cut]);
}
}
for(int cut=1;cut<n;cut++){
for(int column=0;column<n;column++){
horizontal[cut][column]=wall[cut-1][column]!=wall[cut][column];
}
}
int best=0;
int bestTop=0,bestLeft=0,bestBottom=0,bestRight=0;
for(int top=1;top<n-1;top++){
for(int bottom=top+1;bottom<n;bottom++){
int left=-1;
for(int right=1;right<n;right++){
if(right>1&&(!horizontal[top][right-1]||!horizontal[bottom][right-1])){
left=-1;
}
if(blocked[bottom][right]==blocked[top][right]){
if(left==-1){
left=right;
}
else if((bottom-top)*(right-left)>best){
best=(bottom-top)*(right-left);
bestTop=top+1;
bestLeft=left+1;
bestBottom=bottom;
bestRight=right;
}
}
}
}
}
cout<<best<<' '<<bestTop<<' '<<bestLeft<<' '<<bestBottom<<' '<<bestRight<<'\n';
}