Largest Window without Breaking Bricks
Autumn Tournament (2014)
Submission name: window.cpp
Problem summary
An even N×N wall is tiled by labelled 1×2 domino bricks. Remove a largest axis-aligned square made entirely of whole bricks. The square must not touch the wall’s outer boundary. Output its side length and its top-left cell; at least one valid window exists.
Input
N, then N rows of N brick labels. Each label occurs in the two adjacent cells occupied by that brick.
Output
Print side row column, using 1-based cell coordinates. Any largest window is accepted.
Constraints
N is even and 4≤N≤2000; brick labels range from 1 to N²/2; at least one valid interior square exists.
Worked example
Official sample input with the other valid maximum window: remove bricks 10 and 11. The source prints 2 3 2, removing bricks 6 and 7; both outputs are correct.
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
2 4 4
Solution analysis
- Use grid corners, not cell centers. A corner (r,c) lies after r rows and c columns; both coordinates must be between 1 and N−1 so the hole stays strictly inside. A horizontal unit boundary is usable precisely when the cells above and below it have different labels. A vertical unit boundary similarly compares the cells on its left and right.
- Precompute the numbers of consecutive usable unit boundaries extending right, left, down and up from every internal corner. The minimum of right and down is forward[r,c], the largest possible top and left sides from this top-left corner. The minimum of left and up is backward[r,c], the largest bottom and right sides ending at this bottom-right corner.
- A square’s two opposite corners lie on one down-right diagonal. Index that diagonal by t. A candidate top-left t and bottom-right j form a valid square if j−t≤forward[t] and j−t≤backward[j]. Its side must be even because an odd-area square cannot contain only whole dominoes.
- Sweep j along each diagonal. Keep earlier corners active until t+forward[t] expires, using a min-heap. Two ordered sets separate even and odd t. Among active corners of the same parity as j, find the first t≥j−backward[j]. This earliest feasible corner gives the largest square ending at j. Insert j only after querying, to exclude zero-sized squares.
- In the sample, top-left grid corner (2,1) and bottom-right (4,3) have four clear sides of length 2, enclosing cells starting at row 3,column 2. A larger square would cross at least one brick or touch the wall boundary.
Why it works
A square cuts no brick exactly when all four boundary runs are usable. The two opposite-corner minima encode those four requirements without inspecting the interior. The active set enforces the top-left bound, the lower_bound enforces the bottom-right bound, and parity enforces an even side. Every valid square is queried when its bottom-right corner is processed; selecting the earliest feasible top-left maximizes its side. Taking the maximum across all diagonals therefore finds a largest valid window.
Watch out. The square must not touch the outer wall: process corners 1..N−1 only. Cell coordinates in the answer are one greater than the top-left corner coordinates. Comparing identical adjacent labels detects a broken brick; do not confuse this with whether the removed interior is connected. Use compact run tables to keep memory reasonable.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: A square cuts no brick exactly when all four boundary runs are usable. The two opposite-
// corner minima encode those four requirements without inspecting the interior.
#include<algorithm>
#include<cstdint>
#include<functional>
#include<iostream>
#include<queue>
#include<set>
#include<utility>
#include<vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
vector<int>brick(n*n);
for(int&label:brick){
cin>>label;
}
int stride=n+1;
vector<uint16_t>right(stride*stride),left(right.size());
vector<uint16_t>down(right.size()),up(right.size());
auto cell=[&](int r,int c){
return brick[r*n+c];
};
auto index=[&](int r,int c){
return r*stride+c;
};
for(int r=1;r<n;r++){
for(int c=n-1;c>=1;c--){
if(cell(r-1,c)!=cell(r,c)){
right[index(r,c)]=right[index(r,c+1)]+1;
}
}
for(int c=1;c<n;c++){
if(cell(r-1,c-1)!=cell(r,c-1)){
left[index(r,c)]=left[index(r,c-1)]+1;
}
}
}
for(int c=1;c<n;c++){
for(int r=n-1;r>=1;r--){
if(cell(r,c-1)!=cell(r,c)){
down[index(r,c)]=down[index(r+1,c)]+1;
}
}
for(int r=1;r<n;r++){
if(cell(r-1,c-1)!=cell(r-1,c)){
up[index(r,c)]=up[index(r-1,c)]+1;
}
}
}
int best=0,bestRow=0,bestColumn=0;
auto sweep=[&](int startRow,int startColumn){
set<int>active[2];
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>expiry;
for(int j=0,r=startRow,c=startColumn;r<n&&c<n;j++,r++,c++){
while(!expiry.empty()&&expiry.top().first<j){
int t=expiry.top().second;
active[t%2].erase(t);
expiry.pop();
}
int backward=min(left[index(r,c)],up[index(r,c)]);
auto first=active[j%2].lower_bound(j-backward);
if(first!=active[j%2].end()&&j-*first>best){
best=j-*first;
bestRow=startRow+*first+1;
bestColumn=startColumn+*first+1;
}
int forward=min(right[index(r,c)],down[index(r,c)]);
if(forward>=2){
active[j%2].insert(j);
expiry.push({j+forward,j});
}
}
};
for(int r=1;r<n;r++){
sweep(r,1);
}
for(int c=2;c<n;c++){
sweep(1,c);
}
cout<<best<<' '<<bestRow<<' '<<bestColumn<<'\n';
}