<!DOCTYPE html>
<html><head>
<title>Contest Results</title>
<META HTTP-EQUIV="EXPIRES" CONTENT="0">
<META HTTP-EQUIV="CACHE-CONTROL" CONTENT="NO-CACHE">
<META HTTP-EQUIV="PRAGMA" CONTENT="NO-CACHE">
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]}
});
</script>
<script type="text/javascript" src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>
<script src="https://google-code-prettify.googlecode.com/svn/loader/run_prettify.js"></script>
</head>
<body>
(Analysis by Andi Qu, Benjamin Qi, Danny Mittal)
<p>For any subrectangle we can construct a graph where there exists an edge
separating two cells if they are of different colors. For example, the graph for
<p><pre>
AAB
BBA
BBB
</pre>
<p>would be
<p><pre>
._._._.
| | |
._._._.
| | |
. . ._.
| |
._._._.
</pre>
<p>The main idea is to use
<a href='https://en.wikipedia.org/wiki/Euler_characteristic'>Euler's formula</a> for
planar graphs. This equation states that <span class='math'>$F = E - V + C + 1$</span>, where
<p><ul><li><span class='math'>$F\implies$</span># of faces</li><li><span class='math'>$E\implies$</span># of edges</li><li><span class='math'>$V\implies$</span># of vertices</li><li><span class='math'>$C\implies$</span># of connected components</li></ul>
<p>So in the above example,
<p><ul><li><span class='math'>$F=4+1=5,$</span> where <span class='math'>$1$</span> comes from the face consisting of everything outside of
the subrectangle.</li><li><span class='math'>$E=18,$</span> the total number of cell borders (horizontal and vertical unit
segments).</li><li><span class='math'>$V=4\cdot 4=16,$</span> one for each cell corner (dot).</li><li><span class='math'>$C=2,$</span> one for the vertex that has no edges coming out of it and one for the
remaining vertices.</li></ul>
<p>So the answer for each candidate is just <span class='math'>$E - V + C.$</span> <span class='math'>$V$</span> depends only on the
dimensions of the subrectangle, and <span class='math'>$E$</span> can be found in <span class='math'>$O(1)$</span> time using prefix
sums. The main challenge is finding <span class='math'>$C$</span>, the number of connected components
completely inside the subrectangle (plus one for the component corresponding to
the border).
<p>We can use the same concept as
<a href='https://csacademy.com/contest/romanian-ioi-2017-selection-1/task/rooms/'>Romanian
IOI Selection 2017 "Rooms"</a>, which was the inspiration for this problem. For
each component, call its topmost vertex "special". Then the number of special
vertices that lie strictly within the border of the subrectangle is a good
approximation for the number of components completely inside the subrectangle,
and can also be computed via prefix sums.
<p>However, it is possible that a component does not lie completely within the
subrectangle but its special vertex does, leading to an overcount. Notice that
such components must have at least one vertex on the border of the
subrectangle, so simply traverse the border of the subrectangle and delete all
such components from the count. This solution takes <span class='math'>$\mathcal{O}(MN + Q(M + N))$</span>
time in total.
<p><pre class='prettyprint'>
/*
Paint by Letters
Andi Qu
- F = E - V + C + 1
- Every corner of a cell is a node
- Every side of a cell is an edge if it is between 2 different colours
- DFS to find connected components
- To check if a component is completely inside a query rectangle, traverse
the perimeter of the rectangle
- Complexity: O(MN + Q(M + N))
*/
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
using namespace std;
int n, m, q;
char grid[2001][2001];
pair<int, int> special[2002][2002], d[4]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int s_pref[2002][2002], v_pref[2002][2002], h_pref[2002][2002];
bool deleted[2002][2002];
bool inside(int x, int y, int nx, int ny) {
if (!(~nx && ~ny && nx <= n + 1 && ny <= m + 1)) return false;
if (nx == x + 1) return grid[x][y] != grid[x][y - 1];
if (nx == x - 1) return grid[nx][y] != grid[nx][y - 1];
if (ny == y + 1) return grid[x][y] != grid[x - 1][y];
return grid[x][ny] != grid[x - 1][ny];
}
bool outside(int x, int y, int x1, int y1, int x2, int y2) {
int a = special[x][y].first, b = special[x][y].second;
if (a > x1 && a <= x2 && b > y1 && b <= y2 && !deleted[a][b]) {
deleted[a][b] = true;
return true;
}
return false;
}
void deactivate(int x, int y) {
int a = special[x][y].first, b = special[x][y].second;
deleted[a][b] = false;
}
void dfs(int x, int y) {
FOR(i, 0, 4) {
int nx = x + d[i].first, ny = y + d[i].second;
if (inside(x, y, nx, ny)) {
if (nx == x + 1) v_pref[x][y] = 1;
else if (nx == x - 1) v_pref[nx][y] = 1;
else if (ny == y + 1) h_pref[x][y] = 1;
else h_pref[x][ny] = 1;
if (!special[nx][ny].first) {
special[nx][ny] = special[x][y];
dfs(nx, ny);
}
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
// freopen("paint.in", "r", stdin);
// freopen("paint.out", "w", stdout);
cin >> n >> m >> q;
FOR(i, 1, n + 1) FOR(j, 1, m + 1) cin >> grid[i][j];
FOR(i, 1, n + 2) FOR(j, 1, m + 2) if (!special[i][j].first) {
s_pref[i][j] = 1;
special[i][j] = {i, j};
dfs(i, j);
}
FOR(i, 1, n + 2) FOR(j, 1, m + 2) {
s_pref[i][j] += s_pref[i - 1][j] + s_pref[i][j - 1] - s_pref[i - 1][j - 1];
v_pref[i][j] += v_pref[i - 1][j] + v_pref[i][j - 1] - v_pref[i - 1][j - 1];
h_pref[i][j] += h_pref[i - 1][j] + h_pref[i][j - 1] - h_pref[i - 1][j - 1];
}
while (q--) {
int x1, x2, y1, y2;
cin >> x1 >> y1 >> x2 >> y2;
if (x1 > x2) swap(x1, x2);
if (y1 > y2) swap(y1, y2);
int E = v_pref[x2][y2] - v_pref[x2][y1] - v_pref[x1 - 1][y2] + v_pref[x1 - 1][y1] +
h_pref[x2][y2] - h_pref[x2][y1 - 1] - h_pref[x1][y2] + h_pref[x1][y1 - 1];
int V = (x2 - x1) * (y2 - y1);
int C = s_pref[x2][y2] - s_pref[x2][y1] - s_pref[x1][y2] + s_pref[x1][y1];
// Delete connected components not entirely inside the query rectangle
FOR(i, x1, x2 + 2) {
if (outside(i, y2 + 1, x1, y1, x2, y2)) C--;
if (outside(i, y1, x1, y1, x2, y2)) C--;
}
FOR(i, y1, y2 + 2) {
if (outside(x2 + 1, i, x1, y1, x2, y2)) C--;
if (outside(x1, i, x1, y1, x2, y2)) C--;
}
FOR(i, x1, x2 + 2) {
deactivate(i, y2 + 1);
deactivate(i, y1);
}
FOR(i, y1, y2 + 2) {
deactivate(x2 + 1, i);
deactivate(x1, i);
}
cout << E - V + C + 1 << '\n';
}
return 0;
}
</pre>
<p>A similar approach involves treating cells as vertices, two adjacent cells of
the same color as an edge, and a cycle of a single color (as described in the
problem statement) which contains no smaller cycles as a face. Then we can use
Euler's formula to count the number of connected components (<span class='math'>$V-E+F$</span>). Partial
credit corresponded to no faces, faces of a single type (a <span class='math'>$2\times 2$</span> square of
a single color), and faces of two types (in addition to the one previously
mentioned, a <span class='math'>$3\times 3$</span> square with the border of a single color and the
center square of a different color).
<p>Some additional problems for which you can use Euler's formula can be found
<a href='https://usaco.guide/adv/eulers-formula'>here.</a>
<p>A completely different approach is to simply optimize th
评论0