Largest Free Notice Rectangle
National Olympiad — Regional round (2016 season)
Submission name: maxnotice.cpp
Problem summary
Find the largest free axis-aligned rectangle on a board with rectangular notices. Touching borders is permitted but overlapping interiors is not.
Input
L H, then N, then N rows x y width height.
Output
The maximum free area.
Constraints
3 ≤ L,H ≤ 100; 0 ≤ N ≤ 16; notices fit inside the board.
Worked example
Input and output for the worked example discussed below.
Input
12 8 2 2 0 3 3 6 1 5 4
Output
36
Solution analysis
- Mark occupied square-centimetre cells. Every relevant boundary is integral, so a maximal free rectangle can be extended to integer board or notice boundaries. The cell model loses no optimum.
- Enumerate the top and bottom row of the proposed rectangle. Maintain a flag for each column: it remains usable only while all cells between these rows are free. Extending the bottom row requires checking one new cell per column.
- For a fixed vertical span, scan the longest consecutive run of usable columns. Multiply its length by the span height and maximize over every row pair. In the sample the full-width strip y=5…8 gives area12×3=36.
Why it works
For each row pair a rectangle is free exactly when it uses consecutive usable columns. The longest such run maximizes its width. Every optimal rectangle has one of the enumerated vertical spans, so the maximum of these exact span optima is globally optimal.
Watch out. Do not combine separated free runs. Use half-open occupied cell ranges so touching existing borders remains legal.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
int main(){
int width;
int height;
int count;
cin>>width>>height>>count;
vector<vector<bool>>occupied(height,vector<bool>(width));
for(int i=0;i<count;i++){
int x;
int y;
int a;
int b;
cin>>x>>y>>a>>b;
for(int row=y;row<y+b;row++){
for(int column=x;column<x+a;column++){
occupied[row][column]=true;
}
}
}
int answer=0;
for(int top=0;top<height;top++){
vector<bool>usable(width,true);
for(int bottom=top;bottom<height;bottom++){
int run=0;
for(int column=0;column<width;column++){
// Every cell in this vertical span must remain empty.
usable[column]=usable[column]&&!occupied[bottom][column];
run=usable[column]?run+1:0;
answer=max(answer,run*(bottom-top+1));
}
}
}
cout<<answer<<'\n';
}