Quality of Living
Given an R C grid where each cell has a unique quality rating from 1 to RC, find an H W subgrid whose median is minimized. The median of HW values is the HW/2 -th smallest value.
Problem Statement
Rendered from the "Problem Summary" section in the LaTeX write-up.
Given an $R \times C$ grid where each cell has a unique quality rating from $1$ to $RC$, find an $H \times W$ subgrid whose median is minimized. The median of $HW$ values is the $\lceil HW/2 \rceil$-th smallest value.
Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
Solution
Algorithm: Binary Search on the Median
Binary search on the answer $m$. For a candidate median $m$, define an indicator matrix: \[ B[i][j] =
\] Let $k = \lceil HW / 2 \rceil$. There exists an $H \times W$ subgrid with median $\le m$ if and only if some subgrid contains at least $k$ cells with values $\le m$, i.e., $\sum B[i][j] \ge k$ over that subgrid. This is checked via 2D prefix sums.
Correctness
Lemma.
The predicate ``there exists an $H \times W$ subgrid with median $\le m$'' is monotone in $m$.
Proof.
If the predicate holds for $m$, it holds for all $m' \ge m$, since increasing $m$ can only increase the count of values $\le m'$ in any subgrid. Hence binary search applies.
Theorem.
The smallest $m$ for which the predicate holds is the minimum achievable median.
Proof.
At the transition point $m^*$, some subgrid has at least $k$ values $\le m^*$, so its median is $\le m^*$. For $m^* - 1$, no subgrid has $k$ values $\le m^* - 1$, so every subgrid has median $\ge m^*$.
Complexity
Time: $O(RC \log(RC))$ --- $O(\log(RC))$ binary search iterations, each taking $O(RC)$ to build prefix sums and check all subgrids.
Space: $O(RC)$.
Code
C++ solution used for this page.
// IOI 2010 - Quality of Living
// Binary search on the median value + 2D prefix sums.
// O(R * C * log(R * C)) time.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int R, C, H, W;
cin >> R >> C >> H >> W;
vector<vector<int>> grid(R, vector<int>(C));
for (int i = 0; i < R; i++)
for (int j = 0; j < C; j++)
cin >> grid[i][j];
int total = H * W;
int medianPos = (total + 1) / 2; // 1-indexed rank of the median
// Check: is there an HxW subgrid with at least medianPos values <= m?
auto check = [&](int m) -> bool {
vector<vector<int>> psum(R + 1, vector<int>(C + 1, 0));
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
psum[i + 1][j + 1] = (grid[i][j] <= m ? 1 : 0)
+ psum[i][j + 1] + psum[i + 1][j] - psum[i][j];
}
}
for (int i = H; i <= R; i++) {
for (int j = W; j <= C; j++) {
int cnt = psum[i][j] - psum[i - H][j]
- psum[i][j - W] + psum[i - H][j - W];
if (cnt >= medianPos) return true;
}
}
return false;
};
int lo = 1, hi = R * C, ans = hi;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (check(mid)) {
ans = mid;
hi = mid - 1;
} else {
lo = mid + 1;
}
}
cout << ans << "\n";
return 0;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.