# New Sample: 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.*

All-Russian School Olympiad in Informatics 2025–2026, Final Stage<br>
“Artificial Intelligence” profile, Tour 1, Moscow, 23 March 2026<br>
Task E

*The official solutions file repeats each statement before its solution; the statement is in the task statement file. The marking criteria below come from the “Marking criteria for the first tour” pages at the end of the same file.*

## Solution

**Answer:** $R_1^2 = \dfrac{2R_0^2}{1 + R_0^2}$.

Let $\widehat{y}_i = f(x_i)$ (the prediction); $SSE_0 = \sum\limits_{i=1}^{n} (y_i - \widehat{y}_i)^2$ (the sum of squared errors), $SST_0 = \sum\limits_{i=1}^{n} (y_i - \bar{y})^2$ (the total sum of squares). Then $R_0^2 = 1 - \dfrac{SSE_0}{SST_0}$.

Similarly, we define the quantities $SSE_1$ and $SST_1$ for the second model.

**Lemma 1.** *The model trained on the combined sample coincides with the original one, and therefore $SSE_1 = SSE_0$.*

*Proof.* For the model $f$, the errors $(\widehat{y}_i - f(x_i))^2$ at the added points $(x_i, \widehat{y}_i)$ are equal to zero, and for the original points the sum of squared errors is the smallest possible. Hence, the minimum on the combined sample is attained at the same parameter values (and so the models coincide). $\square$

**Lemma 2.** *The following equalities hold:*

$$\sum_{i=1}^{n} (y_i - \widehat{y}_i) = 0 \quad \text{and} \quad \sum_{i=1}^{n} x_i (y_i - \widehat{y}_i) = 0.$$

*Proof.* The point $(a, b)$ is chosen by the least-squares method, that is, it is the point at which the function

$$F(u, v) = \sum_{i=1}^{n} (y_i - u x_i - v)^2$$

takes its smallest value. Hence, if we fix $u = a$, the resulting quadratic function of the variable $v$ attains its smallest value at the point $b$. This means that the $v$-coordinate of the vertex of the corresponding parabola equals $b$, that is,

$$-b = \frac{1}{n} \left( \sum_{i=1}^{n} (a x_i - y_i) \right) \implies 0 = \sum_{i=1}^{n} (a x_i + b) - \sum_{i=1}^{n} y_i = \sum_{i=1}^{n} (\widehat{y}_i - y_i).$$

Arguing similarly for $v = b$, we obtain the second stated relation:

$$-a \cdot \sum_{i=1}^{n} x_i^2 = \sum_{i=1}^{n} (b - y_i) x_i \implies 0 = \sum_{i=1}^{n} x_i (a x_i + b - y_i) = x_i (\widehat{y}_i - y_i).$$

$\square$

**Lemma 3.** *The equality $SST_1 = 2SST_0 - SSE_0$ holds.*

*Proof.* By Lemma 2, the equality $\dfrac{1}{n} \sum\limits_{i=1}^{n} \widehat{y}_i = \bar{y}$ holds. Hence,

$$SST_1 = \sum_{i=1}^{n} (y_i - \bar{y})^2 + \sum_{i=1}^{n} (\widehat{y}_i - \bar{y})^2 = SST_0 + \sum_{i=1}^{n} (\widehat{y}_i - \bar{y})^2.$$

Moreover, $y_i - \bar{y} = (y_i - \widehat{y}_i) + (\widehat{y}_i - \bar{y})$. Let us square all such equalities and then add them up. We obtain

$$SST_0 = \sum_{i=1}^{n} (y_i - \widehat{y}_i)^2 + \sum_{i=1}^{n} (\widehat{y}_i - \bar{y})^2 + 2 \sum_{i=1}^{n} (y_i - \widehat{y}_i)(\widehat{y}_i - \bar{y}).$$

The last term is zero. Indeed, let us use Lemma 2 as follows:

$$\sum_{i=1}^{n} (y_i - \widehat{y}_i)(\widehat{y}_i - \bar{y}) = \sum_{i=1}^{n} (y_i - \widehat{y}_i)\widehat{y}_i = a \sum_{i=1}^{n} x_i (y_i - \widehat{y}_i) + b \sum_{i=1}^{n} (y_i - \widehat{y}_i) = 0.$$

Then $SST_0 = SSE_0 + \sum\limits_{i=1}^{n} (\widehat{y}_i - \bar{y})^2$, which gives the required equality. $\square$

Putting together the results of Lemmas 1–3, we have:

$$R_1^2 = 1 - \frac{SSE_1}{SST_1} = 1 - \frac{SSE_0}{2SST_0 - SSE_0} = \frac{2(SST_0 - SSE_0)}{2SST_0 - SSE_0}.$$

Dividing the numerator and the denominator by $SST_0$, we obtain the stated answer:

$$R_1^2 = \frac{2\left(1 - \frac{SSE_0}{SST_0}\right)}{2 - \frac{SSE_0}{SST_0}} = \frac{2R_0^2}{1 + R_0^2}.$$

**Comment.** Lemma 2 can be proved differently, using the fact that the partial derivatives of the function $F(u, v)$ at the point $(a, b)$ are equal to zero.

## Marking criteria

Well-known properties of linear regression are accepted without proof **provided they are stated correctly**.

A. Correct answer: 10 points.

B. It is proved that $f = g$: 10 points.

- If it is only stated that $f = g$, 5 points are awarded.
- If the proof relies on properties of linear regression, the property of the added data that allows one to conclude that the coefficients of the models are equal must be stated explicitly.
- If this is used and not even stated, no points are awarded under criterion $B$.
- No additional points are awarded for concluding that the numerators in the expressions for the coefficient of determination are equal.

C1. The relations between $y_i, x_i, f(x_i)$ are established (Lemma 2): 10 points.

C2. Expressions for $a$ and $b$ are obtained (the formula for the linear regression coefficients), with a proof that the means are equal: 10 points.

- **Both** relations must be established (in the form given in C1 or C2), and the equality of the means of the old and the new sample must be stated explicitly. For obtaining any one of the relations, 5 points are awarded for part $C$.

M. Lemma 3 (or an analogous equality) is used in the solution without proof: 15 points are deducted.

- No points are awarded for algebraic transformations that do not lead to a dependence of $R_1^2$ **only** on $R_0^2$.