ICPC 2021 - G. Mosaic Browsing
We are given a large grid (the mosaic) and a smaller grid (the motif). The motif may contain zeroes, which act as wildcards. We must output every top-left position where the motif matches the corresponding subgrid of...
Source-first archive entry
This page is built from the copied files in competitive_programming/icpc/2021/G-mosaic-browsing. Edit
competitive_programming/icpc/2021/G-mosaic-browsing/solution.tex to update the written solution and
competitive_programming/icpc/2021/G-mosaic-browsing/solution.cpp to update the implementation.
The website does not replace those files with hand-maintained HTML. It reads the copied source tree during the build and exposes the exact files below.
Problem Statement
Copied statement text kept beside the solution archive for direct reference.
Problem G
Mosaic Browsing
Time limit: 6 seconds
The International Center for the Preservation of Ceramics (ICPC) is searching for motifs in some ancient
mosaics. According to the ICPC’s definition, a mosaic is a rectangular grid where each grid square
contains a colored tile. A motif is similar to a mosaic but some of the grid squares can be empty. Figure
G.1 shows an example motif and mosaic.
The rows of an rq × cq mosaic are numbered 1 to rq from top to bottom, and the columns are numbered
1 to cq from left to right.
A contiguous rectangular subgrid of the mosaic matches the motif if every tile of the motif matches the
color of the corresponding tile of the subgrid. Formally, an rp × cp motif appears in an rq × cq mosaic
at position (r, c) if for all 1 ≤ i ≤ rp , 1 ≤ j ≤ cp , the tile (r + i − 1, c + j − 1) exists in the mosaic and
either the square (i, j) in the motif is empty or the tile at (i, j) in the motif has the same color as the tile
at (r + i − 1, c + j − 1) in the mosaic.
Given the full motif and mosaic, find all occurrences of the motif in the mosaic.
Figure G.1: Motif (left) and mosaic (right) of Sample Input 1.
Input
The first line of input contains two integers rp and cp , where rp and cp (1 ≤ rp , cp ≤ 1 000) are the
number of rows and columns in the motif. Then rp lines follow, each with cp integers in the range
[0, 100], denoting the color of the motif at that position. A value of 0 denotes an empty square.
The next line of input contains two integers rq and cq where rq and cq (1 ≤ rq , cq ≤ 1 000) are the
number of rows and columns in the mosaic. Then rq lines follow, each with cq integers in the range
[1, 100], denoting the color of the mosaic at that position.
Output
On the first line, output k, the total number of matches. Then output k lines, each of the form r c where
r is the row and c is the column of the top left tile of the match. Sort matches by increasing r, breaking
ties by increasing c.
Sample Input 1 Sample Output 1
2 2 3
1 0 1 1
0 1 1 3
3 4 2 2
1 2 1 2
2 1 1 1
2 2 1 3
Editorial
Rendered from the copied solution.tex file. The original TeX source remains
available below.
A One-Dimensional Identity
For one aligned pair of cells, let \[ p = \text{motif value}, \qquad q = \text{mosaic value}. \]
We want this cell to be valid exactly when either \[ p = 0 \] or \[ p = q. \]
The expression \[ p(q-p)^2 \] does exactly that:
if $p=0$, it is zero regardless of $q$;
if $p \ne 0$, it is zero exactly when $q=p$;
otherwise it is a positive integer.
So an alignment is valid if and only if \[ \sum p(q-p)^2 = 0 \] over all aligned cells.
Expanding gives \[ \sum p q^2 - 2 \sum p^2 q + \sum p^3. \] The third sum depends only on the motif. The first two are cross-correlations, which can be computed by FFT.
Turning the 2D Grid into 1D
Flatten the mosaic in row-major order.
Flatten the motif in row-major order as well, but after each motif row insert \[ c_q - c_p \] zeroes, so that every motif row occupies exactly one full mosaic row in the flattened string.
Then placing the motif at top-left position $(r,c)$ in the 2D mosaic is exactly the same as aligning the flattened padded motif with the flattened mosaic starting at index \[ (r-1)c_q + (c-1). \]
This padding is the crucial trick: it prevents the end of one motif row from accidentally matching the beginning of the next mosaic row.
Using Convolution
Let the padded motif be $P$ and the flattened mosaic be $Q$. For each valid offset $s$, we need \[ \sum_i P_i (Q_{s+i} - P_i)^2 = 0. \]
Expanding: \[ \sum_i P_i Q_{s+i}^2 - 2 \sum_i P_i^2 Q_{s+i} + \sum_i P_i^3. \]
We compute:
the correlation of $P$ with $Q^2$;
the correlation of $P^2$ with $Q$.
Each correlation is obtained by reversing the motif array and performing one ordinary convolution.
Algorithm
Read the motif and mosaic.
Flatten the mosaic into a 1D array $Q$, and also build $Q^2$.
Flatten the motif with row padding into $P$, and also build $P^2$ and the constant \[ C = \sum_i P_i^3. \]
Reverse $P$ and $P^2$.
Compute \[ A = \text{conv}(\text{rev}(P), Q^2), \qquad B = \text{conv}(\text{rev}(P^2), Q). \]
For every legal top-left position $(r,c)$, let \[ s = (r-1)c_q + (c-1). \] The alignment score is \[ A[s + |P| - 1] - 2B[s + |P| - 1] + C. \] This score is zero exactly for matches.
Correctness Proof
We prove that the algorithm outputs exactly all valid occurrences of the motif.
Lemma 1.
For a single aligned cell with motif value $p$ and mosaic value $q$, the quantity \[ p(q-p)^2 \] is zero if and only if the cell matches, meaning either $p=0$ or $p=q$.
Proof.
If $p=0$, the value is clearly zero. If $p \ne 0$, then a square is zero only when $q-p=0$, i.e. when $q=p$. In every other case it is strictly positive. □
Lemma 2.
For one alignment of the motif against the mosaic, the total score \[ \sum_i P_i(Q_{s+i}-P_i)^2 \] is zero if and only if the full alignment is a valid match.
Proof.
By Lemma 1, every summand is a nonnegative integer and equals zero exactly when the corresponding cell matches. Therefore the whole sum is zero exactly when every aligned cell matches. □
Lemma 3.
The padded row-major flattening preserves exactly the legal 2D alignments.
Proof.
Each motif row is padded to length $c_q$, so shifting by one row in the flattened motif corresponds to shifting by exactly one full mosaic row. Therefore aligning the padded motif at flattened offset \[ (r-1)c_q + (c-1) \] compares motif cell $(i,j)$ with mosaic cell $(r+i-1,c+j-1)$, which is exactly the desired 2D alignment. No cross-row wraparound can occur because of the inserted zero padding. □
Lemma 4.
For every legal starting position, the algorithm computes the correct alignment score.
Proof.
The term \[ \sum_i P_iQ_{s+i}^2 \] is the correlation of $P$ with $Q^2$, and similarly \[ \sum_i P_i^2Q_{s+i} \] is the correlation of $P^2$ with $Q$. Reversing the motif arrays converts each correlation into an ordinary convolution, and the index $s+|P|-1$ extracts the correct aligned value. Adding the constant $\sum_i P_i^3$ gives exactly the expanded score from Lemma 2. □
Theorem.
The algorithm outputs exactly all positions where the motif appears in the mosaic.
Proof.
By Lemma 3, every legal 2D placement corresponds to one tested flattened offset. By Lemma 4, the algorithm computes the exact score for that placement, and by Lemma 2 the score is zero exactly when the placement is a valid match. Therefore the reported positions are exactly the motif occurrences. □
Complexity Analysis
Let \[ N = r_q c_q, \qquad M = (r_p-1)c_q + c_p. \] We perform two FFT-based convolutions of size $O(N+M)$, so the total running time is \[ O((N+M)\log(N+M)). \] The memory usage is linear in the FFT size.
Implementation Notes
The score is always a nonnegative integer, so after FFT rounding errors it is safe to accept a match when the computed value is very close to zero.
If $r_p > r_q$ or $c_p > c_q$, there are no legal placements at all.
Code
Exact copied C++ implementation from solution.cpp.
#include <bits/stdc++.h>
using namespace std;
namespace {
using cd = complex<double>;
const double PI = acos(-1.0);
void fft(vector<cd>& a, bool invert) {
int n = static_cast<int>(a.size());
for (int i = 1, j = 0; i < n; ++i) {
int bit = n >> 1;
for (; j & bit; bit >>= 1) {
j ^= bit;
}
j ^= bit;
if (i < j) {
swap(a[i], a[j]);
}
}
for (int len = 2; len <= n; len <<= 1) {
double angle = 2.0 * PI / len * (invert ? -1.0 : 1.0);
cd wlen(cos(angle), sin(angle));
for (int i = 0; i < n; i += len) {
cd w(1.0, 0.0);
for (int j = 0; j < len / 2; ++j) {
cd u = a[i + j];
cd v = a[i + j + len / 2] * w;
a[i + j] = u + v;
a[i + j + len / 2] = u - v;
w *= wlen;
}
}
}
if (invert) {
for (cd& value : a) {
value /= n;
}
}
}
vector<double> convolution(const vector<double>& a, const vector<double>& b) {
int n = 1;
while (n < static_cast<int>(a.size() + b.size() - 1)) {
n <<= 1;
}
vector<cd> fa(n), fb(n);
for (int i = 0; i < static_cast<int>(a.size()); ++i) {
fa[i] = a[i];
}
for (int i = 0; i < static_cast<int>(b.size()); ++i) {
fb[i] = b[i];
}
fft(fa, false);
fft(fb, false);
for (int i = 0; i < n; ++i) {
fa[i] *= fb[i];
}
fft(fa, true);
vector<double> result(a.size() + b.size() - 1);
for (int i = 0; i < static_cast<int>(result.size()); ++i) {
result[i] = fa[i].real();
}
return result;
}
void solve() {
int rp, cp;
cin >> rp >> cp;
vector<vector<int>> pattern(rp, vector<int>(cp));
for (int i = 0; i < rp; ++i) {
for (int j = 0; j < cp; ++j) {
cin >> pattern[i][j];
}
}
int rq, cq;
cin >> rq >> cq;
vector<vector<int>> mosaic(rq, vector<int>(cq));
for (int i = 0; i < rq; ++i) {
for (int j = 0; j < cq; ++j) {
cin >> mosaic[i][j];
}
}
if (rp > rq || cp > cq) {
cout << 0 << '\n';
return;
}
int text_len = rq * cq;
int pattern_len = (rp - 1) * cq + cp;
vector<double> text(text_len), text_sq(text_len);
for (int i = 0; i < rq; ++i) {
for (int j = 0; j < cq; ++j) {
int idx = i * cq + j;
text[idx] = mosaic[i][j];
text_sq[idx] = static_cast<double>(mosaic[i][j]) * mosaic[i][j];
}
}
vector<double> pattern_flat(pattern_len, 0.0);
vector<double> pattern_sq(pattern_len, 0.0);
long long pattern_cube_sum = 0;
for (int i = 0; i < rp; ++i) {
for (int j = 0; j < cp; ++j) {
int idx = i * cq + j;
int value = pattern[i][j];
pattern_flat[idx] = value;
pattern_sq[idx] = static_cast<double>(value) * value;
pattern_cube_sum += 1LL * value * value * value;
}
}
reverse(pattern_flat.begin(), pattern_flat.end());
reverse(pattern_sq.begin(), pattern_sq.end());
vector<double> term1 = convolution(pattern_flat, text_sq);
vector<double> term2 = convolution(pattern_sq, text);
vector<pair<int, int>> matches;
int offset = pattern_len - 1;
for (int r = 0; r + rp <= rq; ++r) {
for (int c = 0; c + cp <= cq; ++c) {
int start = r * cq + c;
double score = term1[start + offset] - 2.0 * term2[start + offset] + pattern_cube_sum;
if (fabs(score) < 0.5) {
matches.push_back({r + 1, c + 1});
}
}
}
cout << matches.size() << '\n';
for (const pair<int, int>& match : matches) {
cout << match.first << ' ' << match.second << '\n';
}
}
} // namespace
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
Source Files
Exact copied source-of-truth files. Edit solution.tex for the write-up and solution.cpp for the implementation.
\documentclass[11pt]{article}
\usepackage[margin=1in]{geometry}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{enumitem}
\title{ICPC World Finals 2021\\G. Mosaic Browsing}
\author{}
\date{}
\begin{document}
\maketitle
\section*{Problem Summary}
We are given a large grid (the mosaic) and a smaller grid (the motif). The motif may contain zeroes,
which act as wildcards. We must output every top-left position where the motif matches the corresponding
subgrid of the mosaic.
The naive check of every position against every motif cell is too slow for $1000 \times 1000$ grids.
\section*{A One-Dimensional Identity}
For one aligned pair of cells, let
\[
p = \text{motif value}, \qquad q = \text{mosaic value}.
\]
We want this cell to be valid exactly when either
\[
p = 0
\]
or
\[
p = q.
\]
The expression
\[
p(q-p)^2
\]
does exactly that:
\begin{itemize}[leftmargin=*]
\item if $p=0$, it is zero regardless of $q$;
\item if $p \ne 0$, it is zero exactly when $q=p$;
\item otherwise it is a positive integer.
\end{itemize}
So an alignment is valid if and only if
\[
\sum p(q-p)^2 = 0
\]
over all aligned cells.
Expanding gives
\[
\sum p q^2 - 2 \sum p^2 q + \sum p^3.
\]
The third sum depends only on the motif. The first two are cross-correlations, which can be computed by
FFT.
\section*{Turning the 2D Grid into 1D}
Flatten the mosaic in row-major order.
Flatten the motif in row-major order as well, but after each motif row insert
\[
c_q - c_p
\]
zeroes, so that every motif row occupies exactly one full mosaic row in the flattened string.
Then placing the motif at top-left position $(r,c)$ in the 2D mosaic is exactly the same as aligning the
flattened padded motif with the flattened mosaic starting at index
\[
(r-1)c_q + (c-1).
\]
This padding is the crucial trick: it prevents the end of one motif row from accidentally matching the
beginning of the next mosaic row.
\section*{Using Convolution}
Let the padded motif be $P$ and the flattened mosaic be $Q$. For each valid offset $s$, we need
\[
\sum_i P_i (Q_{s+i} - P_i)^2 = 0.
\]
Expanding:
\[
\sum_i P_i Q_{s+i}^2
- 2 \sum_i P_i^2 Q_{s+i}
+ \sum_i P_i^3.
\]
We compute:
\begin{itemize}[leftmargin=*]
\item the correlation of $P$ with $Q^2$;
\item the correlation of $P^2$ with $Q$.
\end{itemize}
Each correlation is obtained by reversing the motif array and performing one ordinary convolution.
\section*{Algorithm}
\begin{enumerate}[leftmargin=*]
\item Read the motif and mosaic.
\item Flatten the mosaic into a 1D array $Q$, and also build $Q^2$.
\item Flatten the motif with row padding into $P$, and also build $P^2$ and the constant
\[
C = \sum_i P_i^3.
\]
\item Reverse $P$ and $P^2$.
\item Compute
\[
A = \text{conv}(\text{rev}(P), Q^2),
\qquad
B = \text{conv}(\text{rev}(P^2), Q).
\]
\item For every legal top-left position $(r,c)$, let
\[
s = (r-1)c_q + (c-1).
\]
The alignment score is
\[
A[s + |P| - 1] - 2B[s + |P| - 1] + C.
\]
This score is zero exactly for matches.
\end{enumerate}
\section*{Correctness Proof}
We prove that the algorithm outputs exactly all valid occurrences of the motif.
\paragraph{Lemma 1.}
For a single aligned cell with motif value $p$ and mosaic value $q$, the quantity
\[
p(q-p)^2
\]
is zero if and only if the cell matches, meaning either $p=0$ or $p=q$.
\paragraph{Proof.}
If $p=0$, the value is clearly zero. If $p \ne 0$, then a square is zero only when $q-p=0$, i.e. when
$q=p$. In every other case it is strictly positive. \qed
\paragraph{Lemma 2.}
For one alignment of the motif against the mosaic, the total score
\[
\sum_i P_i(Q_{s+i}-P_i)^2
\]
is zero if and only if the full alignment is a valid match.
\paragraph{Proof.}
By Lemma 1, every summand is a nonnegative integer and equals zero exactly when the corresponding cell
matches. Therefore the whole sum is zero exactly when every aligned cell matches. \qed
\paragraph{Lemma 3.}
The padded row-major flattening preserves exactly the legal 2D alignments.
\paragraph{Proof.}
Each motif row is padded to length $c_q$, so shifting by one row in the flattened motif corresponds to
shifting by exactly one full mosaic row. Therefore aligning the padded motif at flattened offset
\[
(r-1)c_q + (c-1)
\]
compares motif cell $(i,j)$ with mosaic cell $(r+i-1,c+j-1)$, which is exactly the desired 2D alignment.
No cross-row wraparound can occur because of the inserted zero padding. \qed
\paragraph{Lemma 4.}
For every legal starting position, the algorithm computes the correct alignment score.
\paragraph{Proof.}
The term
\[
\sum_i P_iQ_{s+i}^2
\]
is the correlation of $P$ with $Q^2$, and similarly
\[
\sum_i P_i^2Q_{s+i}
\]
is the correlation of $P^2$ with $Q$. Reversing the motif arrays converts each correlation into an
ordinary convolution, and the index $s+|P|-1$ extracts the correct aligned value. Adding the constant
$\sum_i P_i^3$ gives exactly the expanded score from Lemma 2. \qed
\paragraph{Theorem.}
The algorithm outputs exactly all positions where the motif appears in the mosaic.
\paragraph{Proof.}
By Lemma 3, every legal 2D placement corresponds to one tested flattened offset. By Lemma 4, the
algorithm computes the exact score for that placement, and by Lemma 2 the score is zero exactly when the
placement is a valid match. Therefore the reported positions are exactly the motif occurrences. \qed
\section*{Complexity Analysis}
Let
\[
N = r_q c_q, \qquad M = (r_p-1)c_q + c_p.
\]
We perform two FFT-based convolutions of size $O(N+M)$, so the total running time is
\[
O((N+M)\log(N+M)).
\]
The memory usage is linear in the FFT size.
\section*{Implementation Notes}
\begin{itemize}[leftmargin=*]
\item The score is always a nonnegative integer, so after FFT rounding errors it is safe to accept a
match when the computed value is very close to zero.
\item If $r_p > r_q$ or $c_p > c_q$, there are no legal placements at all.
\end{itemize}
\end{document}
#include <bits/stdc++.h>
using namespace std;
namespace {
using cd = complex<double>;
const double PI = acos(-1.0);
void fft(vector<cd>& a, bool invert) {
int n = static_cast<int>(a.size());
for (int i = 1, j = 0; i < n; ++i) {
int bit = n >> 1;
for (; j & bit; bit >>= 1) {
j ^= bit;
}
j ^= bit;
if (i < j) {
swap(a[i], a[j]);
}
}
for (int len = 2; len <= n; len <<= 1) {
double angle = 2.0 * PI / len * (invert ? -1.0 : 1.0);
cd wlen(cos(angle), sin(angle));
for (int i = 0; i < n; i += len) {
cd w(1.0, 0.0);
for (int j = 0; j < len / 2; ++j) {
cd u = a[i + j];
cd v = a[i + j + len / 2] * w;
a[i + j] = u + v;
a[i + j + len / 2] = u - v;
w *= wlen;
}
}
}
if (invert) {
for (cd& value : a) {
value /= n;
}
}
}
vector<double> convolution(const vector<double>& a, const vector<double>& b) {
int n = 1;
while (n < static_cast<int>(a.size() + b.size() - 1)) {
n <<= 1;
}
vector<cd> fa(n), fb(n);
for (int i = 0; i < static_cast<int>(a.size()); ++i) {
fa[i] = a[i];
}
for (int i = 0; i < static_cast<int>(b.size()); ++i) {
fb[i] = b[i];
}
fft(fa, false);
fft(fb, false);
for (int i = 0; i < n; ++i) {
fa[i] *= fb[i];
}
fft(fa, true);
vector<double> result(a.size() + b.size() - 1);
for (int i = 0; i < static_cast<int>(result.size()); ++i) {
result[i] = fa[i].real();
}
return result;
}
void solve() {
int rp, cp;
cin >> rp >> cp;
vector<vector<int>> pattern(rp, vector<int>(cp));
for (int i = 0; i < rp; ++i) {
for (int j = 0; j < cp; ++j) {
cin >> pattern[i][j];
}
}
int rq, cq;
cin >> rq >> cq;
vector<vector<int>> mosaic(rq, vector<int>(cq));
for (int i = 0; i < rq; ++i) {
for (int j = 0; j < cq; ++j) {
cin >> mosaic[i][j];
}
}
if (rp > rq || cp > cq) {
cout << 0 << '\n';
return;
}
int text_len = rq * cq;
int pattern_len = (rp - 1) * cq + cp;
vector<double> text(text_len), text_sq(text_len);
for (int i = 0; i < rq; ++i) {
for (int j = 0; j < cq; ++j) {
int idx = i * cq + j;
text[idx] = mosaic[i][j];
text_sq[idx] = static_cast<double>(mosaic[i][j]) * mosaic[i][j];
}
}
vector<double> pattern_flat(pattern_len, 0.0);
vector<double> pattern_sq(pattern_len, 0.0);
long long pattern_cube_sum = 0;
for (int i = 0; i < rp; ++i) {
for (int j = 0; j < cp; ++j) {
int idx = i * cq + j;
int value = pattern[i][j];
pattern_flat[idx] = value;
pattern_sq[idx] = static_cast<double>(value) * value;
pattern_cube_sum += 1LL * value * value * value;
}
}
reverse(pattern_flat.begin(), pattern_flat.end());
reverse(pattern_sq.begin(), pattern_sq.end());
vector<double> term1 = convolution(pattern_flat, text_sq);
vector<double> term2 = convolution(pattern_sq, text);
vector<pair<int, int>> matches;
int offset = pattern_len - 1;
for (int r = 0; r + rp <= rq; ++r) {
for (int c = 0; c + cp <= cq; ++c) {
int start = r * cq + c;
double score = term1[start + offset] - 2.0 * term2[start + offset] + pattern_cube_sum;
if (fabs(score) < 0.5) {
matches.push_back({r + 1, c + 1});
}
}
}
cout << matches.size() << '\n';
for (const pair<int, int>& match : matches) {
cout << match.first << ' ' << match.second << '\n';
}
}
} // namespace
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}