Soccer Stadium
Problem Statement Given an N N grid where some cells contain trees (F[r][c] = 1), find the largest regular stadium: a set of empty cells such that any two cells can be connected by at most two straight kicks (horizont...
Problem Statement
Rendered from the "Problem Statement" section in the LaTeX write-up.
Given an $N \times N$ grid where some cells contain trees ($F[r][c] = 1$), find the largest regular stadium: a set of empty cells such that any two cells can be connected by at most two straight kicks (horizontal or vertical line segments, with every intermediate cell in the stadium).
Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
Characterization
Definition.
A regular stadium is a set $\mathcal{S}$ of empty cells such that for every pair of cells $(r_1, c_1), (r_2, c_2) \in \mathcal{S}$, there exists a cell $(r_m, c_m) \in \mathcal{S}$ with:
the entire row segment from $(r_1, c_1)$ to $(r_1, c_m)$ (or the column segment from $(r_1, c_1)$ to $(r_m, c_1)$) lies in $\mathcal{S}$, and
the entire column (or row) segment from $(r_m, c_m)$ to $(r_2, c_2)$ lies in $\mathcal{S}$.
definition
Theorem (Column-interval relay).
thm:relay Every optimal regular stadium can be described as follows: there exists a contiguous column interval $[c_l, c_r]$ (the relay zone) such that the stadium consists of cells from rows that contain no tree in $[c_l, c_r]$, extended left and right as far as possible in each row.
Formally, for each row $r$ where $F[r][c] = 0$ for all $c \in [c_l, c_r]$, the stadium includes the maximal contiguous empty segment in row $r$ that contains $[c_l, c_r]$.
Proof (Proof sketch).
In a regular stadium, any two cells must connect via at most two kicks. Consider the set of columns that every included row-segment covers. The intersection of all row-segments' column ranges must be non-empty (otherwise two cells in rows with disjoint column ranges cannot connect in two kicks). This common column interval serves as the relay zone.
Any two cells $(r_1, c_1)$ and $(r_2, c_2)$ can then connect via: kick 1 along row $r_1$ to some column $c \in [c_l, c_r]$, then kick 2 along column $c$ to row $r_2$, then (if needed) kick along row $r_2$ to $c_2$ --- but since both rows span $[c_l, c_r]$, the column kick from $(r_1, c)$ to $(r_2, c)$ must pass through only rows included in the stadium.
For the column segment to be fully inside the stadium, every row between $r_1$ and $r_2$ must include column $c$. This means we can only include a contiguous vertical block of rows (those with $[c_l, c_r]$ clear). More precisely, the included rows need not be contiguous: we need every row between any two included rows (at column $c$) to also be included. So the set of included rows, restricted to any relay column, must be contiguous.
Actually, we only need some relay column $c \in [c_l, c_r]$ such that the column of included rows at $c$ covers all row-pairs. Since the included rows are exactly those where $[c_l, c_r]$ is tree-free, and between any two such rows a row with a tree in $[c_l, c_r]$ would block the column kick, we must ensure the included rows form contiguous blocks per relay column. The simplest valid structure is: enumerate all $(c_l, c_r)$ pairs, for each find the maximal set of contiguous rows where $[c_l, c_r]$ is tree-free, and extend each row as far as possible.
Corollary.
The optimal stadium size can be found by enumerating all $O(N^2)$ column-interval pairs $(c_l, c_r)$ and computing the total cells for each in $O(N)$ time.
Algorithm
Precompute, for each cell $(r, c)$, the leftmost and rightmost extent of the contiguous empty segment in row $r$ containing $c$.
Precompute row prefix sums to check whether $[c_l, c_r]$ is tree-free in row $r$ in $O(1)$.
For each pair $(c_l, c_r)$ with $0 \le c_l \le c_r < N$:
For each row $r$: if $[c_l, c_r]$ is tree-free, find the maximal empty segment containing $[c_l, c_r]$ and add its length.
The rows must form contiguous blocks for the column kicks to work. We sum over all rows in each maximal contiguous block and take the maximum block-sum, or --- since the relay allows reaching any row through the relay columns --- we need all included rows to be mutually reachable. The simplest correct approach: only include rows that form one contiguous block (no tree row in between at any relay column), or sum all qualifying rows and verify connectivity.
Additionally check single-row and single-column stadiums, and the maximal-rectangle baseline.
In fact, the simplest correct $O(N^3)$ approach that handles all cases: for each $(c_l, c_r)$, sum the extended row lengths over all qualifying rows. Two cells in different qualifying rows can always connect: go along row to some column $c \in [c_l, c_r]$, then down column $c$ to the target row (all intermediate rows also qualify since they must be tree-free in $[c_l, c_r]$ for this to work). So we also need the qualifying rows to be contiguous. We handle this by finding maximal contiguous runs.
Complexity
Time: $O(N^3)$. There are $O(N^2)$ column-interval pairs; for each, a single pass over $N$ rows.
Space: $O(N^2)$ for the precomputed arrays.
Theorem (Correctness).
The algorithm correctly finds the largest regular stadium.
Proof.
By Theorem thm:relay, every regular stadium has a relay column interval $[c_l, c_r]$ such that each row's contribution is a contiguous empty segment spanning $[c_l, c_r]$, and the contributing rows form a contiguous vertical block (so that column kicks between any two rows stay within the stadium).
Our algorithm enumerates all possible relay intervals and, for each, finds the best contiguous vertical block of qualifying rows. Within such a block, any two cells connect in at most two kicks: a horizontal kick to a relay column, then a vertical kick to the target row (and optionally a horizontal kick in the target row).
Since we maximize over all choices, the algorithm finds the global optimum.
Code
C++ solution used for this page.
#include <bits/stdc++.h>
using namespace std;
// IOI 2023 - Soccer Stadium
// N x N grid with trees. Find largest "regular stadium": a set of empty cells
// where any two cells connect via at most 2 straight kicks (axis-aligned
// segments fully within the set).
//
// Approaches combined:
// 1. Single relay column: for each column c, sum maximal row intervals through c.
// 2. Single relay row: symmetric to approach 1.
// 3. Maximal empty rectangle (histogram method).
// 4. Relay column interval [c1,c2]: for each (c1,c2) pair, find rows where
// [c1,c2] is fully empty, extend each row's interval left/right.
// This is the key O(N^3) approach that covers all optimal stadiums.
int biggest_stadium(int N, vector<vector<int>> F) {
int best = 0;
// Precompute for each cell: leftmost and rightmost empty extent in its row
vector<vector<int>> left_ext(N, vector<int>(N));
vector<vector<int>> right_ext(N, vector<int>(N));
for (int r = 0; r < N; r++) {
// Left extent: furthest left we can go from (r, c) within empty cells
left_ext[r][0] = (F[r][0] == 0) ? 0 : -1;
for (int c = 1; c < N; c++) {
if (F[r][c] == 1)
left_ext[r][c] = -1;
else
left_ext[r][c] = (left_ext[r][c - 1] >= 0) ? left_ext[r][c - 1] : c;
}
// Right extent
right_ext[r][N - 1] = (F[r][N - 1] == 0) ? N - 1 : -1;
for (int c = N - 2; c >= 0; c--) {
if (F[r][c] == 1)
right_ext[r][c] = -1;
else
right_ext[r][c] = (right_ext[r][c + 1] >= 0) ? right_ext[r][c + 1] : c;
}
}
// Approach 1: single relay column
for (int c = 0; c < N; c++) {
int total = 0;
for (int r = 0; r < N; r++) {
if (F[r][c] == 0)
total += right_ext[r][c] - left_ext[r][c] + 1;
}
best = max(best, total);
}
// Approach 2: single relay row
// Precompute vertical extents
vector<vector<int>> top_ext(N, vector<int>(N));
vector<vector<int>> bot_ext(N, vector<int>(N));
for (int c = 0; c < N; c++) {
top_ext[0][c] = (F[0][c] == 0) ? 0 : -1;
for (int r = 1; r < N; r++) {
if (F[r][c] == 1)
top_ext[r][c] = -1;
else
top_ext[r][c] = (top_ext[r - 1][c] >= 0) ? top_ext[r - 1][c] : r;
}
bot_ext[N - 1][c] = (F[N - 1][c] == 0) ? N - 1 : -1;
for (int r = N - 2; r >= 0; r--) {
if (F[r][c] == 1)
bot_ext[r][c] = -1;
else
bot_ext[r][c] = (bot_ext[r + 1][c] >= 0) ? bot_ext[r + 1][c] : r;
}
}
for (int r = 0; r < N; r++) {
int total = 0;
for (int c = 0; c < N; c++) {
if (F[r][c] == 0)
total += bot_ext[r][c] - top_ext[r][c] + 1;
}
best = max(best, total);
}
// Approach 3: maximal empty rectangle (histogram)
vector<int> height(N, 0);
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++)
height[c] = (F[r][c] == 0) ? height[c] + 1 : 0;
stack<int> stk;
for (int c = 0; c <= N; c++) {
int h = (c < N) ? height[c] : 0;
while (!stk.empty() && height[stk.top()] > h) {
int idx = stk.top(); stk.pop();
int width = stk.empty() ? c : c - stk.top() - 1;
best = max(best, height[idx] * width);
}
stk.push(c);
}
}
// Approach 4: relay column interval [c1, c2]
// Precompute prefix sums for each row to check if [c1,c2] is tree-free
vector<vector<int>> row_prefix(N, vector<int>(N + 1, 0));
for (int r = 0; r < N; r++)
for (int c = 0; c < N; c++)
row_prefix[r][c + 1] = row_prefix[r][c] + F[r][c];
for (int c1 = 0; c1 < N; c1++) {
for (int c2 = c1; c2 < N; c2++) {
int total = 0;
for (int r = 0; r < N; r++) {
// Check if [c1, c2] is entirely empty in row r
if (row_prefix[r][c2 + 1] - row_prefix[r][c1] == 0) {
// Extend left and right from [c1, c2]
int left = left_ext[r][c1];
int right = right_ext[r][c2];
total += right - left + 1;
}
}
best = max(best, total);
}
}
return best;
}
int main() {
int N;
scanf("%d", &N);
vector<vector<int>> F(N, vector<int>(N));
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
scanf("%d", &F[i][j]);
printf("%d\n", biggest_stadium(N, F));
return 0;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.