# Municipal Stage (Moscow) of the All-Russian School Olympiad 2025/26 in Artificial Intelligence, Grades 9–11: Answers and Solutions
*English translation by SOTA – AI Community of the Russian original. Organisers who would like this translation removed can email sota.ai.community@gmail.com.*
*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). Running header on every page: "Analysis of the tasks of the municipal stage of the VsOSh 2025/26 in artificial intelligence — grades 9–11".*
**Maximum score for the olympiad — 600**
## Task 1. Maths in a Chatbot
Dima chose two natural numbers $a$ and $b$. Then he sent an AI model a request to compute $a^b$. He wrote this expression on a piece of paper, photographed it and uploaded the photograph. Because of the untidy handwriting, the model recognised the expression as $a \cdot b$ and computed exactly that. As a result, its answer turned out to be 110 less than the correct one.
What answer did the model give?
**Answer:** 15
**Scoring criterion:** exact match of the answer — 100 points
**Maximum score for the task — 100**
**Solution.** From the statement we obtain $a^b - ab = 110$. Hence 110 is divisible by $a$. This leaves the options $a = 1, 2, 5, 10, 11, 22, 55, 110$.
$a = 1$: $1 - b = 110$ — no solutions.
$a = 2$: $2^{b-1} - b = 55$. The left-hand side is less than 55 for $b \le 6$ and greater than 55 for $b \ge 7$.
$a = 5$: $5^{b-1} - b = 22$. The left-hand side is less than 22 for $b \le 2$, equal to 22 for $b = 3$, and greater than 22 for $b \ge 4$.
$a = 10$: $10^{b-1} - b = 11$. The left-hand side is greater than 11 for $b \ge 3$; $b = 1, 2$ do not work. The cases $a = 11, 22, 55, 110$ are dealt with in the same way as the previous case.
## Task 2. Maximum Trace over All Permutations
An $n \times m$ matrix is what we call a table of numbers consisting of $n$ rows and $m$ columns. Matrices are multiplied by the "row by column" rule. If
$$
M = \begin{pmatrix} p & q \\ r & s \end{pmatrix}, \qquad N = \begin{pmatrix} u & v \\ w & x \end{pmatrix},
$$
then
$$
MN = \begin{pmatrix} pu + qw & pv + qx \\ ru + sw & rv + sx \end{pmatrix}.
$$
The sum of the diagonal elements (the trace) of a matrix is the number $tr\begin{pmatrix} p & q \\ r & s \end{pmatrix} = p + s$.
You are given the matrix
$$
A = \begin{pmatrix} -1 & 4 \\ 5 & 10 \end{pmatrix}.
$$
You are also given the numbers $-4, -5, 20, 25$. Consider all 24 matrices $B$ of the form
$$
B = \begin{pmatrix} x & y \\ z & w \end{pmatrix},
$$
in which $x, y, z, w$ is some permutation of the numbers $-4, -5, 20, 25$. For each such $B$, consider the products $AB$ and $BA$.
**a)** Find the largest possible value of $tr(AB)$.
**Answer:** 339
**Scoring criterion:** exact match of the answer — 50 points
**b)** Find the largest possible value of $tr(BA)$.
**Answer:** 339
**Scoring criterion:** exact match of the answer — 50 points
**Maximum score for the task — 100**
**Solution.** A useful property: for any square matrices of the same size, $\mathrm{tr}(AB) = \mathrm{tr}(BA)$. Therefore, it suffices to maximise $\mathrm{tr}(AB)$.
Let $B = \begin{pmatrix} x & y \\ z & w \end{pmatrix}$. Then
$$
AB = \begin{pmatrix} -1 & 4 \\ 5 & 10 \end{pmatrix} \begin{pmatrix} x & y \\ z & w \end{pmatrix} = \begin{pmatrix} -x + 4z & -y + 4w \\ 5x + 10z & 5y + 10w \end{pmatrix},
$$
and therefore
$$
\mathrm{tr}(AB) = (-x + 4z) + (5y + 10w) = -x + 4z + 5y + 10w.
$$
We need to assign $-5, -4, 20, 25$ to $x, y, z, w$ so as to maximise the linear form with coefficients $-1, 5, 4, 10$ respectively. By the rearrangement inequality, the maximum is attained when the largest coefficient is matched with the largest number, and so on in decreasing order:
$$
10 \leftrightarrow 25, \quad 5 \leftrightarrow 20, \quad 4 \leftrightarrow (-4), \quad (-1) \leftrightarrow (-5).
$$
That is, $w = 25$, $y = 20$, $z = -4$, $x = -5$. Then
$$
\mathrm{tr}(AB) = -(-5) + 4 \cdot (-4) + 5 \cdot 20 + 10 \cdot 25 = 5 - 16 + 100 + 250 = 339.
$$
By the property $\mathrm{tr}(AB) = \mathrm{tr}(BA)$, the same value is obtained for $BA$ as well.
Thus, the largest possible sum of the diagonal elements is 339.
## Task 3. Minimisation of $L_1$ and $L_2$
You are tuning the simplest possible regression model, which always predicts the same number $c$ (a constant model). You are given a set of true values:
$$
y = \{1, 2, 3, 9, 10, 10\}.
$$
Consider two quality functions: $L_1(c) = \sum_i |y_i - c|$ and $L_2(c) = \sum_i (y_i - c)^2$.
**a)** Find the value $c_1$ that minimises $L_1(c)$. If there are several optimal values, give the smallest of them as your answer.
**Answer:** 3
**Scoring criterion:** exact match of the answer — 50 points
**b)** Find the value $c_2$ that minimises $L_2(c)$. If there are several optimal values, give the smallest of them as your answer.
**Answer:** 35/6
**Scoring criterion:** exact match of the answer — 50 points
**Maximum score for the task — 100**
**Solution.** Let us sort the values: 1, 2, 3, 9, 10, 10.
**a)** *Minimum of $L_1$.*
$L_1(c)$ is minimised at the *median* of the sample. With an even number of elements, the set of optima is the whole segment between the two middle values. Here the middle values are 3 and 9, so the optima are $c \in [3, 9]$. By the rule of the task, we take the smallest:
$$
c_1 = 3.
$$
**b)** *Minimum of $L_2$.*
$L_2(c)$ is a quadratic parabola; the minimum is attained at the *mean*:
$$
c_2 = \frac{1 + 2 + 3 + 9 + 10 + 10}{6} = \frac{35}{6}.
$$
(The optimum is unique, so the instruction to take the "smallest" value changes nothing here.)
## Task 4. Group By
An electronic testing system records the results of pupils' tests, which you can download in [XLSX](https://lab.sirius.online/smt-portal/content/_image/0effa7fbaa0656e1855397104ba75e4b8256540d), [ODS](https://lab.sirius.online/smt-portal/files/08e4f777f83cbbaf61d53b6a61e040ab9cc53a31.ods) or [CSV](https://lab.sirius.online/smt-portal/content/_image/4443dd3559f8649824ea854e28a90a5dc61b554f) format. The file contains five columns:
- `student_id` — the pupil's identifier (integer);
- `subject` — the subject in which the test was taken (string);
- `score` — the score obtained (real number);
- `cheat_flag` — suspicion of cheating (True/False);
- `attempt_no` — the attempt number (integer; 1 means the first attempt).
Perform the following operations on the data:
1. Clean the score column: replace empty values with 0, also replace values less than 0 with 0, and replace values greater than 100 with 100.
2. Delete the rows where `cheat_flag` = True.
3. Keep only the rows that correspond to the first attempt, that is, those where `attempt_no` = 1.
4. For each pupil, compute their average score across subjects: the mean of all `score` values that remain after the operations above.
How many pupils have an average score in the range $60 \leqslant$ `avg_score` $< 80$?
**Answer:** 363
**Scoring criterion:** exact match of the answer — 100 points
**Maximum score for the task — 100**
**Solution.** A solution to the task in Python:
```python
import pandas as pd
df = pd.read_csv("tests.csv")
df["score"] = df["score"].fillna(0)
mask_neg = df["score"] < 0
df.loc[mask_neg, "score"] = 0
mask_high = df["score"] > 100
df.loc[mask_high, "score"] = 100
df = df[df["cheat_flag"] == False]
df = df[df["attempt_no"] == 1]
mean_by_student = df.groupby("student_id")["score"].mean()
cond = (mean_by_student >= 60) & (mean_by_student < 80)
answer = cond.sum()
print(answer)
```
## Task 5. Decision Non-Making Tree
Time limit: 1 second
Memory limit: 256 megabytes
Decision trees are often used in machine learning. Each internal vertex of such a tree corresponds to some question, and each edge corresponds to the choice of an answer (yes/no). In this way, with a few questions, the input data can be split into a fairly large number of classes. Dima's latest project is a decision non-making tree. Its structure is similar to that of a decision tree. It is a complete binary tree of depth $n$. Every vertex, except the vertices of the last level, stores a number $p$ ($0 \leqslant p \leqslant 100$). This number is the probability of the choice: with probability $p$ per cent the algorithm chooses to go left and, accordingly, with probability $100 - p$ per cent it goes right.
Let us agree to denote a move to the left by the digit 0 and a move to the right by the digit 1. Thus, each vertex of the bottom level corresponds to a binary string of length $n$ (the sequence of decisions from the root to the leaf).
The probability of obtaining this string equals the product of the probabilities of all the choices made on the path from the root to the leaf.
Dima has already written a structure for such a tree and wants to test it. For this, he created a tree of depth 3. So it has 7 internal vertices in total. Each vertex has its own number $p$. The layout of these vertices is shown below:
*[Figure: the layout of the vertices; see page 3 of the [original PDF](https://vos.olimpiada.ru/upload/files/Arhive_tasks/2025-26/mun/ai/ans-ai-9-11-mun-msk-25-26.pdf#page=3). Transcription: internal vertices 1–7, edges labelled 0 (left) and 1 (right), leaves labelled with their binary strings.]*
```text
(1)
0 / \ 1
(2) (3)
0 / \ 1 0 / \ 1
(4) (5) (6) (7)
0/ \1 0/ \1 0/ \1 0/ \1
000 001 010 011 100 101 110 111
```
Find the probabilities of all binary strings of length 3 and output the strings in non-decreasing order of probability. If probabilities are equal, the strings must be output in lexicographic order.
### Input format
The first line contains 7 integers $p$ ($0 \leqslant p \leqslant 100$): the probabilities for the vertices, as shown in the figure.
### Output format
Output 8 lines. Each line must contain a binary string of length 3. The strings must be in non-decreasing order of probability. If probabilities are equal, the strings are compared lexicographically.
### Examples
Standard input:
```text
40 90 20 90 100 70 0
```
Standard output:
```text
011
110
001
101
010
100
000
111
```
### Note
In the first test example, the binary strings have the following probabilities:
- 011 – 0.0
- 110 – 0.0
- 001 – 0.036
- 101 – 0.036
- 010 – 0.04
- 100 – 0.084
- 000 – 0.324
- 111 – 0.48
### Solution
In this task, we need to compute the probability of each leaf. Since each such probability is the product of three numbers (the choice probabilities at the vertices), for the comparison it is enough to compare the products of these numbers multiplied by 100 (that is, of the probabilities in per cent). Let us write out all 8 such products explicitly and, for each of them, remember the corresponding three-bit string. After that, we sort the pairs (probability, string) by probability and output the strings in the resulting order. This is the answer.
```cpp
#include
#include
#include
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int p1, p2, p3, p4, p5, p6, p7;
cin >> p1 >> p2 >> p3 >> p4 >> p5 >> p6 >> p7;
int p000 = p1 * p2 * p4;
int p001 = p1 * p2 * (100 - p4);
int p010 = p1 * (100 - p2) * p5;
int p011 = p1 * (100 - p2) * (100 - p5);
int p100 = (100 - p1) * p3 * p6;
int p101 = (100 - p1) * p3 * (100 - p6);
int p110 = (100 - p1) * (100 - p3) * p7;
int p111 = (100 - p1) * (100 - p3) * (100 - p7);
vector> v = {
{p000, "000"},
{p001, "001"},
{p010, "010"},
{p011, "011"},
{p100, "100"},
{p101, "101"},
{p110, "110"},
{p111, "111"}
};
sort(v.begin(), v.end());
for (auto &[p, s] : v) {
cout << s << '\n';
}
return 0;
}
```
**Maximum score for the task — 100**
## Task 6. Heat Map
Time limit: 1 second
Memory limit: 256 megabytes
Slava is preparing a poster for a conference. Unfortunately, his heat map does not fit on the poster at the moment: it is too large. So Slava decided to select some rectangular fragment of the current map and use it for the presentation. Slava's heat map looks like a table of $n$ rows and $m$ columns. The cell at the intersection of the $i$-th row and the $j$-th column has colour $c_{ij}$. There are $k$ colours in use, numbered from 1 to $k$. An example of a similar map is shown on the right. Slava wants to show the whole range of values, so the selected fragment must contain at least one cell of each colour. At the same time, the young speaker wants to minimise the area of the map, because he needs to fit it on the poster.
*[Figure: an example heat map, printed to the right of this text; see page 5 of the [original PDF](https://vos.olimpiada.ru/upload/files/Arhive_tasks/2025-26/mun/ai/ans-ai-9-11-mun-msk-25-26.pdf#page=5).]*
Help him: find a rectangle that can be cut out of his map so that it contains cells of all $k$ colours. It is guaranteed that the original heat map contains cells of all $k$ colours.
### Input format
The first line contains three natural numbers $n, m, k$ ($1 \leqslant n, m \leqslant 250$, $1 \leqslant k \leqslant 20$).
Each of the next $n$ lines contains $m$ natural numbers $c_{ij}$ ($1 \leqslant c_{ij} \leqslant k$).
### Output format
Output 4 numbers $x_1, y_1, x_2, y_2$ that define the rectangle to be cut out. The rectangle is given by its top and bottom rows ($x_1$, $x_2$) and its left and right columns ($y_1$, $y_2$). If there are several ways to cut out a chart of the smallest area, output any of them.
### Examples
Standard input:
```text
3 4 3
1 1 2 2
3 1 1 3
1 2 2 2
```
Standard output:
```text
1 3 2 4
```
### Note
*[Figure: see page 6 of the [original PDF](https://vos.olimpiada.ru/upload/files/Arhive_tasks/2025-26/mun/ai/ans-ai-9-11-mun-msk-25-26.pdf#page=6). Transcription: the $3 \times 4$ map of the example, with three dashed outlines marking rows 2–3 × columns 1–2 (red), rows 1–2 × columns 3–4 (orange) and rows 2–3 × columns 3–4 (purple).]*
| | column 1 | column 2 | column 3 | column 4 |
|:---:|:---:|:---:|:---:|:---:|
| **row 1** | 1 | 1 | 2 | 2 |
| **row 2** | 3 | 1 | 1 | 3 |
| **row 3** | 1 | 2 | 2 | 2 |
All possible ways to cut out a chart of the smallest area for the first example.
### 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
#include
#include
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, k;
cin >> n >> m >> k;
vector> v(n, vector(m));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> v[i][j];
--v[i][j];
}
}
vector>> pref(
k, vector>(n + 1, vector(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 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**