# Heat Map: Official Solution

*English translation by SOTA – AI Community of the Russian original. Organisers who would like this translation removed can email sota.ai.community@gmail.com.*

*Task 6 of the municipal stage (Moscow) of the All-Russian School Olympiad (VsOSh) 2025/26 in artificial intelligence, grades 9–11: official solution (the statement is in a separate file). Original: [ans-ai-9-11-mun-msk-25-26.pdf](https://vos.olimpiada.ru/upload/files/Arhive_tasks/2025-26/mun/ai/ans-ai-9-11-mun-msk-25-26.pdf).*

## Solution

We need to find a rectangular submatrix of minimum area that contains all $k$ colours.

Let us fix the top and bottom rows $l$ and $r$ ($1 \le l \le r \le n$). Then the task reduces to finding the narrowest range of columns that, together with the rows $[l..r]$, covers all the colours.

For convenience, we first compute 2D prefix sums for each colour $c$: $\texttt{pref}[c][i][j]$ is the number of cells of colour $c$ in the rectangle $[1..i] \times [1..j]$. Then the number of cells of colour $c$ in the rectangle with rows $[l..r]$ and columns $[x..y]$ can be obtained in $O(1)$: $\texttt{cnt} = \texttt{pref}[c][r][y] - \texttt{pref}[c][l-1][y] - \texttt{pref}[c][r][x-1] + \texttt{pref}[c][l-1][x-1]$.

Next, we iterate over all pairs of rows $(l, r)$ and apply a two-pointer pass over the columns. We fix the left pointer $x$ and move the right pointer $y$ to the right until the rectangle $[l..r] \times [x..y]$ contains all the colours. As soon as this happens, we can update the answer with the area $(r - l + 1)(y - x + 1)$ and then move $x$ further. Since, for fixed $(l, r)$, the pointer $y$ only increases, the pass over the columns takes $O(m)$.

In total: the prefix sums are computed in $O(knm)$, and iterating over the pairs of rows gives $O(n^2)$ runs of the two pointers, each with $O(m \cdot k)$ for checking that all the colours are present (in this implementation, the check goes through all $k$ colours using the prefix sums). The overall complexity of this version is $O(knm + n^2 mk)$.

```cpp
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, k;
    cin >> n >> m >> k;

    vector<vector<int>> v(n, vector<int>(m));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> v[i][j];
            --v[i][j];
        }
    }

    vector<vector<vector<int>>> pref(
        k, vector<vector<int>>(n + 1, vector<int>(m + 1, 0))
    );

    for (int c = 0; c < k; ++c) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                pref[c][i][j] = pref[c][i - 1][j] + pref[c][i][j - 1]
                              - pref[c][i - 1][j - 1]
                              + (v[i - 1][j - 1] == c);
            }
        }
    }

    int min_area = n * m;
    vector<int> ans(4, -1);

    for (int l = 0; l < n; ++l) {
        for (int r = l; r < n; ++r) {
            int y = 0;
            for (int x = 0; x < m; ++x) {
                if (x > y) y = x;

                while (y < m) {
                    bool ok = true;
                    for (int c = 0; c < k; ++c) {
                        int cnt = pref[c][r + 1][y + 1]
                                - pref[c][l][y + 1]
                                - pref[c][r + 1][x]
                                + pref[c][l][x];
                        if (cnt == 0) {
                            ok = false;
                            break;
                        }
                    }
                    if (ok) break;
                    ++y;
                }

                if (y == m) {
                    x = y;
                    continue;
                }

                int area = (r - l + 1) * (y - x + 1);
                if (area < min_area) {
                    min_area = area;
                    ans = {l + 1, x + 1, r + 1, y + 1};
                }
            }
        }
    }

    cout << ans[0] << ' ' << ans[1] << ' ' << ans[2] << ' ' << ans[3] << '\n';
    return 0;
}
```

**Maximum score for the task — 100**