# Municipal Stage (Moscow) of the All-Russian School Olympiad 2025/26 in Artificial Intelligence, Grades 9–11: Tasks
*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: [tasks-ai-9-11-mun-msk-25-26.pdf](https://vos.olimpiada.ru/upload/files/Arhive_tasks/2025-26/mun/ai/tasks-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 (variant III) — grades 9–11".*
*Translator's note: this paper states points only for Tasks 5 and 6; the official answers give a maximum of 100 points for every task.*
**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?
## 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)$.
**b)** Find the largest possible value of $tr(BA)$.
## 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.
**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.
## 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$?
## 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 2 of the [original PDF](https://vos.olimpiada.ru/upload/files/Arhive_tasks/2025-26/mun/ai/tasks-ai-9-11-mun-msk-25-26.pdf#page=2). 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
**Scoring criterion:** exact match of the answer — 100 points
**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 4 of the [original PDF](https://vos.olimpiada.ru/upload/files/Arhive_tasks/2025-26/mun/ai/tasks-ai-9-11-mun-msk-25-26.pdf#page=4).]*
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 4 of the [original PDF](https://vos.olimpiada.ru/upload/files/Arhive_tasks/2025-26/mun/ai/tasks-ai-9-11-mun-msk-25-26.pdf#page=4). 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.
**Scoring criterion:** exact match of the answer — 100 points
**Maximum score for the task — 100**