1 Ответ
Задание 1. Расстояние между словами
Будем называть словом любую последовательность букв русского алфавита. За одну операцию разрешается сделать одно из трёх действий:
убрать из слова одну любую букву,
добавить в любое место слова любую букву,
заменить любую букву в слове на любую другую букву.
Расстоянием между словами будем называть наименьшее число операций, которое позволяет получить из одного слова
другое. Сколько слов находятся на расстоянии 2 и от слова СТУК, и от слова КУСТЫ?
Решение.
Если некоторое слово находится на расстоянии 2 от слов КУСТЫ и СТУК, то расстояние между словами
КУСТЫ и СТУК не более 4. Изучим кратчайшие «пути» (по количеству операций) между ними.
Покажем, что из слова КУСТЫ можно получить слово СТУК минимум за 4 операции, причём эти 4 операции:
убрать К, У, заменить Ы на У или К и добавить К или У. Если это утверждение доказано, то слова на расстоянии 2 от обоих могут быть только после применения двух из указанных операций, а таких слов 10:
СТЫ, УСТУ, УСТК, КСТУ, КСТК, УСТУЫ, УСТЫК, КСТУЫ, КСТЫК, КУСТУК.
Ответ: 10
Задание 2. След степени матрицы
Матрицей 𝑛 ×𝑚 будем называть таблицу из чисел, состоящую из 𝑛 строк и 𝑚 столбцов. Умножение матриц — это применение правила «строка на столбец». Обычно порядок важен: как правило, 𝑀𝑁 ≠ 𝑁𝑀. Возведением матрицы в степень называют многократное умножение её самой на себя:
𝐴1 = 𝐴, а далее 𝐴𝑘+1 = 𝐴𝑘𝐴.
Найдите сумму левого верхнего и правого нижнего элементов матрицы 𝐴20.
Ответ: 15127
Задание 3. ReLU
Напомним, что:
ReLU(𝑧) = max(0,𝑧).
Рассмотрим функцию действительного аргумента 𝑥:
𝐹(𝑥) = 𝑐 +𝑤1 ·ReLU(𝑥 −𝑡1)+𝑤2 ·ReLU(𝑥 −𝑡2)+···+𝑤2025 ·ReLU(𝑥 −𝑡2025),
где 𝑡1, . . . , 𝑡2025 — попарно различные действительные числа, каждый коэффициент 𝑤𝑖 равен либо +1, либо −1, а 𝑐 —
действительное число.
Какое наибольшее число различных решений может иметь уравнение 𝐹(𝑥) = 0, если известно, что у него конечное число решений?
Ответ: 1013
Задание 4. Чистка журнала заказов маркетплейса
Дан файл с журналом заказов маркетплейса, который вы можете скачать в форматах XLSX, ODS или CSV.
Каждая строка файла содержит три поля в порядке delivery_hours (вещественное число), label (строка) и rating (вещественное число). Сначала оставьте только строки, где время доставки попадает в диапазон: 1 ⩽ delivery_hours ⩽ 96. Затем в столбце label замените все пустые значения модой — самым частым значением этого столбца после фильтрации. Далее нормируйте rating: пусть среди оставшихся строк ratingmin — минимальный рейтинг, а ratingmax — максимальный. Для любой строки её нормированный рейтинг вычисляется по формуле. Сколько строк после всех преобразований одновременно удовлетворяют следующим условиям:
label равен моде;
нормированный рейтинг не меньше 0.8;
delivery_hours ⩽ 48?
Ответ: 711
Задание 5. Сжатие размерности
В машинном обучении часто возникает проблема: данных слишком много, а ресурсов слишком мало. Например, вы обучаете модель для распознавания изображений, и каждое изображение описывается миллионом признаков (по числу пикселей). Если хранить и обрабатывать все признаки, модель получится очень тяжёлой и будет работать медленно. Чтобы справиться с этим, используют приём сжатия размерности. Его смысл — это удалить или преобразовать те признаки, которые не дают новой информации. Например:
если у всех объектов один и тот же цвет фона, то этот признак можно убрать;
если признак не меняется, он не помогает отличать объекты друг от друга.
Рассмотрим упрощённый вариант этой идеи.
Дана выборка объектов а, состоящая из и элементов ај. Каждый объект а; представляется двоичной строкой длины 10.
Получается таблица признаков: строки — объекты, столбцы — признаки (первый бит — первый признак, второй бит — второй признак и так далее). Все признаки бинарные: каждый бит равен либо 0, либо 1.
Если какой-то признак одинаков у всех чисел, он не несёт информации и должен быть удалён.
Сколько признаков останется после удаления одинаковых?
Ответ:
#include <iostream>
#include <vector>
using namespace std ;
int main() {
i os : : sync_with_stdio( false );
cin . tie ( nullptr );
int n;
cin >> n;
vector<int> v(n);
for (int i = 0; i < n; ++i) cin >> v[ i ];
int v_or = v[0];
int v_and = v[0];
for (int i = 0; i < n; ++i) {
v_or |= v[ i ];
v_and &= v[ i ];
}
int a = v_or ^ v_and;
int cnt = 0;
while (a > 0) {
cnt += a % 2;
a /= 2;
}
cout << cnt << ’\n’;
return 0;
}