31:00 Курс — год занятий. Устройство блока: тематический блок из трёх контестов, затем разбор (первые два–три часа занятия), и после разбора у слушателей есть неделя, чтобы дорешать контесты блока, чтобы они пошли в зачёт. Контест — просто набор задач на тему лекции. Кроме контестов есть тест по темам блока.
32:36 Из чего складывается оценка за полугодие: контесты, тесты, экзамен и дистанционные туры (дистуры). Дистур — тур на баллы в формате муниципального или регионального этапа Всероссийской олимпиады; сначала формат муниципального, потом регионального; на дистур даётся две недели, условия задач выкладывать нельзя. Формулу оценки пообещали выслать ближе к экзамену.
33:27 Переводы между параллелями одобряются в любую сторону — достаточно договориться с преподавателями той параллели, в которую хочется перейти (они могут поставить условие, например решить определённые задачи). Организационные вопросы (логины, доступы) — к администраторам курса.
34:17 Просьба решать самостоятельно: современные нейросети могут закрыть контест одним запросом, но смысл курса — научиться; за нарушение возможен бан.
35:09 Занятие состоит из лекции про стандартную библиотеку C++ (многим она уже знакома, но это первое занятие и тему нужно обсудить) и семинара, на котором вместе решаются простые жадные задачи. Весь код ниже — на C++17.
36:19 Основные типы — int, double, float и другие. Кратко про неочевидные (36:59): у long long диапазон от $-2^{63}$ до $2^{63}-1$ (в два раза больше разрядов, чем у int); у int 32 бита и диапазон от $-2^{31}$ до $2^{31}-1$; у unsigned int тоже 32 бита, но диапазон $[0,\,2^{32}-1]$.
38:16 vector и string различаются тем, что строка хранит символы (char), а у вектора тип элементов указывается в угловых скобках.
vector<int> a(5, 5); // конструктор: размер 5, каждый элемент 5
vector<int> b = {5, 5, 5, 5, 5}; // список значений — получится то же самое
// vector<int> c{5, 5}; // осторожно: это два элемента (5 и 5), а не пять пятёрокvector<int>(5, 5) и vector<int>{5, 5} — разные вещи. Круглые скобки вызывают конструктор «размер, значение», фигурные задают список элементов.40:16 auto позволяет не писать тип: компилятор выводит его из выражения. Например, auto x = 5; даст int. Особенно удобно с громоздкими типами: вместо vector<pair<int,int>>::iterator можно написать auto, а по вектору пройти циклом по диапазону.
vector<pair<int, int>> v = {{1, 2}, {3, 4}};
for (auto p : v) cout << p.first << ' ' << p.second << '\n';41:43 Пусть функция печатает вектор. Когда вектор передаётся по значению, он копируется — за $O(n)$ на каждый вызов; можно получить непонятное превышение времени (TL). Если функция не должна менять вектор, его передают по константной ссылке; так же — строки и любые тяжёлые структуры.
void print(const vector<int>& v) { // ссылка: копирования нет
for (int x : v) cout << x << ' ';
cout << '\n';
}43:06 К полю структуры обращаются через точку: p.x. 44:17 Разница между for (auto x : v) и for (auto& x : v): в первом случае каждый элемент копируется. Для int разницы практически нет, а для тяжёлых объектов копирование заметно замедляет цикл (лектор оценил: примерно вдвое); ссылка к тому же позволяет менять элементы.
46:08 vector — динамический массив, умеющий сам расширяться. Объявление: vector<int> v; можно задать список элементов в фигурных скобках либо конструктором «размер, значение» (по умолчанию нули).
47:50 У вектора есть не только размер, но и capacity — сколько элементов поместится в уже выделенную память. size — число лежащих элементов, capacity — размер выделенного блока: это разные числа. Когда size становится равным capacity, при следующем push_back память выделяется заново, и capacity умножается на 2 (по-простому говоря).
push_back работает за амортизированное $O(1)$: удвоений происходит $\approx\log_2 n$, а суммарное число копируемых при этом элементов не больше $1+2+4+\dots<2n$. Точный коэффициент роста стандартом не задан (в разных реализациях 2 или 1,5), но вывод тот же.48:50 push_back(x) добавляет элемент в конец; emplace_back(...) делает то же самое, но конструирует объект на месте: для вектора пар вместо push_back(make_pair(1, 2)) достаточно emplace_back(1, 2). pop_back() удаляет последний элемент, clear() очищает вектор.
vector<pair<int, int>> v;
v.push_back({1, 2});
v.emplace_back(3, 4); // сразу аргументы конструктора пары
v.pop_back();
v.clear();50:37 Итераторы есть у вектора и почти у любого контейнера STL. Базовые: v.begin() — указатель на первый элемент, v.end() — на элемент после последнего. В STL почти всё работает на полуинтервалах [begin, end): левая граница включена, правая — нет.
52:16 У итераторов вектора можно прибавлять и вычитать числа и вычитать друг из друга: v.begin() + 2 — итератор на элемент с индексом 2. Тип итератора громоздкий, поэтому удобно писать auto. 53:49 Итератор можно разыменовать: *it — это сам элемент. Чтобы получить индекс элемента по итератору, нужно вычесть из него v.begin().
vector<int> v = {7, 3, 9, 5, 1};
auto it = v.begin() + 2;
cout << *it << '\n'; // 9
cout << it - v.begin() << '\n'; // 2 — индекс элемента
*it = 10; // через итератор элемент можно изменить54:58 Функция sort(first, last) принимает итераторы начала и конца полуинтервала. Третий параметр — компаратор — необязателен; без него используется оператор < и массив сортируется по возрастанию. Компаратор — булева функция от двух элементов, которая говорит, в каком порядке их расставлять: если a должен стоять раньше b, она возвращает true.
bool cmpDesc(int a, int b) { return a > b; } // по убыванию
sort(v.begin(), v.end()); // по возрастанию
sort(v.begin(), v.end(), cmpDesc); // по убыванию
// сколь угодно сложные условия, например по остатку:
// return a % x < b % x;57:41 Главное условие, которому обязан удовлетворять компаратор: для одной и той же пары элементов он не может говорить «a раньше b» и «b раньше a» одновременно — не может быть, что a должен стоять раньше b и при этом b раньше a.
cmp(a,b) и cmp(b,a) должны возвращать разные значения». Это верно для разных по порядку элементов, но для равных (с точки зрения порядка) обе проверки должны вернуть false, и это нормально. Точное требование — «строгий слабый порядок»: cmp(a,a)=false; из cmp(a,b) следует !cmp(b,a); транзитивность. Типичные ошибки: return a <= b; (при равных элементах оба вызова дают true — возможен вылет за границы массива) и непоследовательное сравнение нескольких полей.58:34 Лямбда — функция, объявленная прямо в месте вызова. В квадратных скобках указывается, какие внешние переменные она захватывает: пустые скобки — ничего не захватываем; [&] — всё по ссылке; [x] — переменную x по значению. Дальше как у обычной функции: параметры и тело.
int x = 7;
sort(v.begin(), v.end(), [&](int a, int b) { return a % x < b % x; });
sort(v.begin(), v.end(), [](int a, int b) { return a > b; });1:00:04 lower_bound и upper_bound — это двоичный поиск, оформленный как готовая функция. Вызов lower_bound(v.begin(), v.end(), x) работает только на отсортированном диапазоне и возвращает итератор на первый элемент, не меньший $x$ (то есть $\ge x$); upper_bound — на первый элемент, строго больший $x$. Границы поиска — любые итераторы, не обязательно begin и end вектора.
vector<int> v = {1, 3, 3, 5, 8};
auto lo = lower_bound(v.begin(), v.end(), 3); // указывает на v[1]: первый элемент ≥ 3
auto hi = upper_bound(v.begin(), v.end(), 3); // указывает на v[3]: первый элемент > 3
int cnt3 = hi - lo; // сколько троек: 2Если все элементы меньше $x$, lower_bound вернёт v.end(); перед разыменованием это нужно проверять.
1:02:26 Определение. Есть массив $a_1,\dots,a_n$. Сжатие координат — преобразование его в массив $b_1,\dots,b_n$ такой, что: для любых $i,j$ из $a_i<a_j$ следует $b_i<b_j$; равные элементы остаются равными; при этом максимум массива $b$ минимален. Иначе говоря, числа заменяются номерами по порядку, а относительный порядок и равенства сохраняются.
1:04:54 Способов много, но самый хороший, «который надо писать»: отсортировать копию массива, воспользоваться функцией unique и для каждого элемента найти его место lower_bound-ом.
1:07:05 unique работает на отсортированном массиве: из каждой группы равных подряд идущих чисел оставляет одно (относительный порядок сохраняется), а остальные переносит в конец массива, и возвращает итератор на место, где заканчиваются уникальные. Сложность $O(n)$: функция один раз проходит массив и пишет в начало только новые значения. После неё «хвост» нужно отрезать.
vector<int> sorted_a = a;
sort(sorted_a.begin(), sorted_a.end());
sorted_a.erase(unique(sorted_a.begin(), sorted_a.end()), sorted_a.end()); // оставили уникальные
for (int& x : a)
x = lower_bound(sorted_a.begin(), sorted_a.end(), x) - sorted_a.begin(); // номер среди уникальных
// итого O(n log n)1:09:26 При разборе на доске в записи кода сначала чего-то не хватало — слушатель заметил, и код поправили. Два корректных варианта: a.resize(unique(a.begin(), a.end()) - a.begin()) и 1:10:04 a.erase(unique(a.begin(), a.end()), a.end()) — второй удаляет всё, начиная с итератора, который вернул unique, до конца.
unique «возвращает размер». Точнее, она возвращает итератор на конец уникальной части; число уникальных элементов — это его разность с begin().1:10:25 next_permutation(begin, end) заменяет диапазон на следующую в лексикографическом порядке перестановку (необязательно настоящую перестановку чисел $1..n$ — подойдёт любой набор). Для $1\,2\,6\,4$ следующей будет $1\,4\,2\,6$: берётся наибольший хвост, который нельзя увеличить; предыдущий элемент меняется на наименьший больший из хвоста, а хвост сортируется по возрастанию. Функция возвращает true, если следующая нашлась, и false, если вся последовательность была наибольшей (тогда массив становится наименьшим — отсортированным).
vector<int> p = {1, 2, 6, 4};
next_permutation(p.begin(), p.end()); // p = {1, 4, 2, 6}
// перебор всех перестановок:
sort(p.begin(), p.end());
do { /* обработать p */ } while (next_permutation(p.begin(), p.end()));1:12:04 iota(begin, end, start) заполняет диапазон значениями $start, start+1, start+2,\dots$ — удобно, чтобы получить тождественную перестановку и затем её переставлять (подробно — на лекции про перебор). 1:13:18 random_shuffle (до C++17) и shuffle(begin, end, gen) перемешивают диапазон случайно, второй — с вашим генератором случайных чисел. 1:14:02 v.assign(n, x) заполняет вектор: делает его размера $n$ из значений $x$.
vector<int> a(5);
iota(a.begin(), a.end(), 0); // 0 1 2 3 4
mt19937 rng(12345);
shuffle(a.begin(), a.end(), rng); // случайная перестановка
a.assign(7, -1); // семь элементов, равных −11:15:00 set — множество: контейнер, хранящий элементы в отсортированном порядке, все элементы уникальны. s.insert(x) добавляет число (если оно уже есть, ничего не происходит), s.erase(x) удаляет (если нет — ничего не происходит).
1:15:51 map хранит по ключу значение: m[key] = value. Ключи уникальны и отсортированы по возрастанию. Во всех этих структурах порядок по умолчанию — по возрастанию; его можно изменить компаратором.
insert, erase, find, lower_bound работают за $O(\log n)$. У unordered_set и unordered_map (хеш-таблицы) операции в среднем $O(1)$, но порядка нет и нельзя сделать lower_bound.1:16:27 В векторе мы писали lower_bound(v.begin(), v.end(), x). Для множества так писать нельзя — вернее, оно заработает, но за $O(n)$: у итераторов множества нет операции «прибавить число», есть только ++ и --, и получить итератор на произвольную позицию за $O(1)$ нельзя. Поэтому у set есть собственный метод s.lower_bound(x) (и upper_bound), работающий за $O(\log n)$. У map тоже есть встроенные lower_bound и upper_bound — они ищут по ключу.
set<int> s = {1, 4, 6, 9};
auto it = s.lower_bound(5); // O(log n): итератор на 6
if (it != s.end()) cout << *it << '\n';
// lower_bound(s.begin(), s.end(), 5) // компилируется, но работает за O(n) — не делайте так
// А ещё: нельзя вычитать итераторы друг из друга (s.end() - s.begin()) — это долго / не скомпилируется.1:18:44 Сжатие координат можно сделать и через множество: закинуть все числа в set (повторы пропадут), затем пройти циклом и присвоить номера $0,1,2,\dots$ по порядку.
1:19:05 Три способа: через lower_bound (итератор не должен быть end и должен указывать на $x$); через s.count(x) — число вхождений (для set это 0 или 1); через s.find(x) — итератор на $x$ либо s.end(). 1:19:48 В C++20 добавили ещё s.contains(x), возвращающий true/false. Всё это работает и в map (find, count, contains).
set<int> s = {1, 4, 6};
bool a1 = s.count(4); // 1
bool a2 = s.find(5) != s.end(); // 0
// bool a3 = s.contains(4); // C++201:21:04 multiset — то же, что set, но один элемент может встречаться несколько раз; элементы отсортированы.
1:21:21 Количество элементов, равных $x$. Метод s.count(x) работает за $O(\log n + k)$, где $k$ — число таких элементов, то есть в худшем случае за $O(n)$ — поэтому в цикле он может «убить» время. Лектор обращает внимание, что лучшего способа средствами одного multiset тут нет; а если нужны именно количества, выручает приём с map (см. ниже).
1:22:43 Удаление. s.erase(x) удаляет все вхождения $x$ (за их число). Чтобы удалить ровно одно вхождение, пишут s.erase(s.find(x)) — стирание по итератору.
multiset<int> ms = {1, 2, 2, 3};
ms.erase(ms.find(2)); // удалили ОДНО вхождение двойки: теперь {1, 2, 3}
ms.erase(2); // удалили ВСЕ двойки: {1, 3}x нет в multiset, то ms.erase(ms.find(x)) стирает end() — неопределённое поведение. Перед стиранием по итератору проверяйте, что итератор не равен end().1:23:52 Пробежаться по всем элементам можно циклом по диапазону или явно итераторами. Обход работает за $O(n)$: каждый шаг ++it в среднем $O(1)$ (по дереву за все $n$ шагов — $O(n)$ в сумме).
for (int x : s) cout << x << ' ';
for (auto it = s.begin(); it != s.end(); ++it) cout << *it << ' ';1:25:42 Нельзя менять множество прямо в таком цикле. Лектор предупреждает: если в цикле по диапазону добавлять или удалять элементы, итераторы «инвалидируются». Поэтому, если нужно пройтись и удалить часть элементов, сначала запоминают, что удалять, а удаляют после цикла. 1:26:02 Альтернатива — искать следующий элемент двоичным поиском (upper_bound): обход получается за $O(n\log n)$, но удалять можно спокойно.
set/map/multiset на самом деле инвалидируются не все итераторы: вставка не портит ни одного итератора, а стирание портит только итераторы на стёртый элемент. Именно поэтому в цикле по диапазону нельзя стирать текущий элемент (после стирания цикл сделает ++ от недействительного итератора). Правильный шаблон стирания «на ходу»: it = s.erase(it), в противном случае ++it. У vector всё строже: любая вставка может перераспределить память и сделать недействительными все итераторы и ссылки.// удалить из множества все чётные числа за один проход
for (auto it = s.begin(); it != s.end(); ) {
if (*it % 2 == 0) it = s.erase(it); // erase возвращает итератор на следующий элемент
else ++it;
}1:27:17 Если программа с multiset не укладывается по времени, можно хранить map<T, int> — каждому значению сопоставлять его количество. Выигрыш виден, когда значений много, а различных мало: миллион единиц, миллион двоек и миллион троек — это три записи в map и три миллиона в multiset.
map<int, int> cnt; // значение → сколько раз встречается
cnt[5]++; // добавить 5
if (--cnt[5] == 0) cnt.erase(5); // удалить одно вхождение пятёрки
// минимум: cnt.begin()->first; максимум: cnt.rbegin()->first1:28:34 stack — «обрезанный» deque: умеет добавить в конец (push), удалить из конца (pop) и взять элемент конца (top). deque умеет работать с обоими концами: push_back, pop_back, push_front, pop_front, а также front() и back() — первый и последний элемент. 1:30:15 queue (очередь) добавляет в конец и удаляет из начала; она пригодится в поиске в ширину (BFS).
deque<int> d;
d.push_back(1); d.push_front(2); // [2, 1]
int f = d.front(), b = d.back(); // 2, 1
d.pop_front(); d.pop_back(); // пусто
queue<int> q;
q.push(5); q.push(7); // добавили в конец
int head = q.front(); q.pop(); // взяли и убрали из начала: 51:31:12 Лектор отмечает: stack почти всегда не нужен — это просто урезанный deque, он не быстрее, поэтому можно пользоваться deque. Важное дополнение: вместо стека подходит и обычный vector (push_back, back, pop_back) — обычно быстрее и без лишних функций.
1:31:55 Если программа читает и печатает много данных (а интерактивной задачи нет), почти всегда стоит включить ускорение: оно уменьшает накладные расходы потоков cin/cout. Помогает, когда программа «не заходит» по времени из-за ввода-вывода. 1:33:03 Лектор отмечает, что некоторые добавляют ещё и cout.tie(0), но на деле это ничего не даёт: достаточно двух строк ниже.
ios::sync_with_stdio(false); // отвязать C++-потоки от C-потоков (stdio)
cin.tie(0); // не сбрасывать cout перед каждым вводом из cinsync_with_stdio(false) нельзя смешивать cin/cout с scanf/printf в одной программе — порядок вывода может нарушиться. В интерактивных задачах ускорение не нужно: там требуется сбрасывать буфер после каждой печати.1:34:05 endl не просто переводит строку: он ещё сбрасывает буфер. '\n' просто обозначает новую строку. endl нужен в интерактивных задачах — когда вы что-то вывели, и потом сразу ждёте ответ. Во всех остальных случаях пишите '\n': это работает быстрее — не намного, но заметно, если строк много.
1:35:27 Перед выводом включают режим фиксированной точки и задают число знаков после запятой. fixed означает, что дробная часть всегда печатается ровно с заданным числом знаков (даже если число целое), а setprecision(6) — это число знаков.
#include <iomanip>
cout << fixed << setprecision(6); // один раз перед выводом
cout << 3.14159265 << '\n'; // 3.141593
cout << 2.0 << '\n'; // 2.0000001:36:39 «Божественный» #include <bits/stdc++.h> подключает почти всю стандартную библиотеку сразу. Он есть в GCC и на всех олимпиадных системах, но не входит в стандарт: на некоторых компиляторах (например, Clang на macOS) его нет.
1:37:50 В заголовок for можно записывать объявление переменной (for (int i = 0; ...)) — это вы знаете. То же можно сделать в if (C++17): переменная живёт только внутри этого if. Лектор добавляет, что пользоваться этим иногда удобно, но обычно не нужно.
if (auto it = s.find(5); it != s.end()) { // C++17: it виден только внутри if/else
cout << "нашли " << *it << '\n';
}1:38:53 На этом лекция заканчивается; затем перерыв на час и семинар, где вместе решают задачи.
2:52:03 Начинают с простых задач: цель — в формате диалога научить решать даже совсем простые жадные задачи, а не просто выдать ответ. Если решение известно сразу, лектор просит дать подумать остальным.
2:54:07 Условие. Дано $n$ коробок-кубов размеров $a_i$. Коробка $i$ помещается в коробку $j$, если $a_i<a_j$ (строгое неравенство — при равенстве было бы «слишком просто»); в одну коробку можно положить не более одной коробки напрямую (внутри может быть цепочка вложенных). Какое минимальное число коробок может остаться снаружи?
2:55:56 Примеры из записи: размеры $5,3,2$ — одна коробка (в пятёрку кладём тройку, в тройку — двойку); $5,3,2,5$ — две коробки. Сортировка решение не портит.
2:56:46 Из зала звучит несколько идей; их проверяют на примере вроде $5,5,6$ (ответ 2, а не 1) — это подводит к наблюдению про одинаковые коробки.
3:02:14 Идея лектора. Важно только максимальное число одинаковых коробок. Если все размеры различны — всё влезает в одну цепочку. В одной цепочке коробок две коробки одинакового размера лежать не могут, поэтому ответ не меньше $k$ — максимальной кратности. 3:03:16 Алгоритм: отсортировать размеры и найти максимальное количество подряд идущих одинаковых; оно и есть ответ.
int minBoxes(vector<int> a) {
sort(a.begin(), a.end());
int best = 0, run = 0; // run — длина текущей группы равных
for (int i = 0; i < (int)a.size(); i++) {
run = (i > 0 && a[i] == a[i - 1]) ? run + 1 : 1;
best = max(best, run);
}
return best; // максимальная кратность
}3:06:02 Лектор проходит пример: размеры $1,2,2,3,3,3,5,5,6$ — максимальное количество одинаковых равно трём (три тройки), значит ответ 3. 3:08:20 Затем та же задача формулируется «строго, без коробок»: массив $a_0,\dots,a_{n-1}$; можно «объединить» $a_i$ и $a_j$, если в $a_i$ ещё ничего не лежит и $a_i>a_j$; нужно получить как можно меньше элементов.
3:10:11 Условие. Студенту надо сдать $n$ экзаменов. Для каждого экзамена есть основная дата $a_i$ и запасная $b_i$ — сдавать можно в любую из этих двух. В зачётку преподаватель записывает основную дату $a_i$ экзамена — независимо от того, в какой день его реально сдали. Экзамены записываются в зачётку в порядке сдачи, и нужно, чтобы записанные даты не убывали. Требуется выбрать для каждого экзамена день сдачи (основной или запасной).
3:12:45 Пример: два экзамена с датами $(a_1,b_1)=(1,2)$ и $(a_2,b_2)=(2,1)$. Если сдать второй в день 1 (запись 2), а первый в день 2 (запись 1), в зачётке будет $2,1$ — убывание, недопустимо. Правильно: первый — в день 1 (запись 1), второй — в день 2 (запись 2).
3:17:19 Идея. Сортируем экзамены по возрастанию пар $(a_i,b_i)$ — это порядок записей в зачётке. Идём по ним и храним $x$ — фактический день последнего сданного экзамена. Для очередного экзамена есть три случая:
3:19:51 Лектор подчёркивает: сложную задачу разбили на три простых случая, а выбор жадный — на каждом шаге делаем $x$ как можно меньше.
struct Exam { int a, b; }; // основная и запасная даты
int examSchedule(vector<Exam> e) { // последний день сдачи или -1, если невозможно
sort(e.begin(), e.end(), [](const Exam& p, const Exam& q) {
return make_pair(p.a, p.b) < make_pair(q.a, q.b); // порядок записей: по a, при равных — по b
});
int x = 0; // день последнего сданного экзамена
for (const Exam& ex : e) {
int lo = min(ex.a, ex.b), hi = max(ex.a, ex.b);
if (lo >= x) x = lo; // сдаём как можно раньше
else if (hi >= x) x = hi;
else return -1; // ни одна дата не подходит
}
return x;
}3:25:38 Условие. Есть $n$ провинций, в $i$-й живёт $a_i$ человек. Две провинции $i$ и $j$ можно объединить в королевство: у него $a_i+a_j$ жителей. Паспорта лень обновлять: королевство берёт название большего, а жители меньшего получают новые паспорта — стоимость объединения $\min(a_i,a_j)$. Мы сами выбираем порядок объединений, нужно объединить все $n$ королевств в одно и минимизировать суммарное число новых паспортов.
3:27:39 Пример $1,2,3$: сначала объединить $1$ и $3$ (стоимость $\min=1$, получилось $4$), потом $4$ и $2$ (стоимость $2$) — всего $3$. Другой порядок: объединить $1$ и $2$ (стоимость $1$), затем $3$ и $3$ (стоимость $3$) — всего $4$.
3:29:09 Ответ: сумма всех чисел, кроме наибольшего (после сортировки — сумма первых $n-1$): объединяем всё в самое большое королевство. Лектор: в любом случае нужно ровно $n-1$ объединений, и минимальный размер первого объединения — минимальное значение, затем следующее и так далее; объединение в самое большое — всегда оптимально.
3:29:54 Усложнение. Теперь при объединении всем жителям обоих королевств выдают новые паспорта: стоимость $a_i+a_j$. Как минимизировать сумму?
3:30:16 Идея лектора: на каждом шаге объединять два наименьших королевства. Лектор честно говорит, что эффект «на каждом шаге оптимально ⇒ в сумме оптимально» не гарантируется автоматически, и доказывать это строго тяжело; интуитивно «два маленьких, два маленьких…» — самое простое решение. 3:33:21 Совет по олимпиаде: за пять часов не нужно строго доказывать всё, что вы пишете. Лектор вспоминает, как на региональном этапе написал пять жадных решений в задаче на динамическое программирование и набрал больше баллов, чем друзья с «нормальной» динамикой: у каждого жадного свои контрпримеры, но в сумме они компенсируют друг друга.
3:34:19 Наивно, $O(n^2)$: после объединения двух минимальных сумма кладётся на своё место сдвигом вправо свопами — вместо сортировки на каждом шаге ($n\log n$ каждый раз) получаем $O(n)$ на шаг: избавились от логарифма, но решение всё равно квадратичное. 3:36:49 Через multiset, $O(n\log n)$: берём два минимальных, стираем, вставляем сумму.
long long mergeCostMultiset(const vector<long long>& a) {
multiset<long long> s(a.begin(), a.end());
long long ans = 0;
while (s.size() > 1) {
long long x = *s.begin(); s.erase(s.begin()); // наименьший
long long y = *s.begin(); s.erase(s.begin()); // следующий
ans += x + y;
s.insert(x + y);
}
return ans;
}3:38:59 За $O(n)$, если числа уже отсортированы. Без такого условия пришлось бы сортировать, и асимптотика всё равно была бы $n\log n$. Заведём второй массив-очередь $B$, куда будем класть получающиеся суммы. Ключевое наблюдение (3:41:15): каждая новая сумма не меньше всех предыдущих (минимальная пара на каждом шаге только растёт), значит очередь $B$ сама остаётся отсортированной. Поэтому два наименьших числа всегда лежат среди «голов» очередей: это либо два первых необработанных числа массива $A$, либо два первых числа очереди $B$, либо по одному из каждой — всего три пары-кандидата.
long long mergeCostTwoQueues(vector<long long> a) { // a отсортирован по неубыванию
int n = a.size(), i = 0; // i — первый необработанный элемент a
deque<long long> q; // очередь сумм: тоже по возрастанию
long long ans = 0;
auto take = [&]() { // достать наименьшее из голов a и q
if (q.empty() || (i < n && a[i] <= q.front())) return a[i++];
long long v = q.front(); q.pop_front(); return v;
};
for (int step = 0; step + 1 < n; step++) {
long long x = take(), y = take();
ans += x + y;
q.push_back(x + y);
}
return ans;
}3:44:25 Почему нельзя класть суммы прямо в массив $A$: мы не знаем, на какое место их ставить, а в очередь $B$ — знаем: каждая следующая сумма не меньше предыдущей и встаёт строго в конец. 3:45:34 Если бы очередная сумма вдруг оказалась меньше предыдущей, значит, на предыдущем шаге взято неоптимальное действие — противоречие с тем, что мы всегда берём минимальную пару.
multiset и на двух очередях) сверены с перебором всех порядков слияний на 1000 случайных массивах (до 6 элементов, значения до 9): ответы совпали.3:47:51 Условие. Есть строка $s$ из нулей и единиц длины $n$ и число $k$. По ней строится строка $v$ той же длины: $v_i=1$, если $s_{i-k}=1$ или $s_{i+k}=1$, и $v_i=0$, если оба равны нулю; если индекса $i-k$ или $i+k$ нет — соответствующий символ считается отсутствующим. Дана $v$ (и $k$); нужно вывести любую подходящую $s$ или сообщить, что такой нет.
3:53:27 На записи сначала обсуждаются подходы «по цепочкам» (определять символы $s$ по уже известным и «прыгать» с шагом $k$), затем 4:04:00 лектор разбирает идею одного из слушателей: смотрим на нули в $v$ — каждый нуль однозначно говорит, что $s_{i-k}=0$ и $s_{i+k}=0$ (если эти индексы существуют). 4:08:57 Остальные символы $s$ можно положить равными единице: они ни на кого, кроме «разрешённых» единиц, не влияют. В конце обязательно проверить: построить $v$ по получившейся $s$ и сравнить с заданной — если не совпало, ответ «нет» (лектор: «вдруг мы где-нибудь запутаемся»).
// возвращает подходящую s или пустую строку, если такой нет
string restore(const string& v, int k) {
int n = v.size();
string s(n, '1'); // всё, что не заставили обнулить, — единицы
for (int i = 0; i < n; i++) if (v[i] == '0') {
if (i - k >= 0) s[i - k] = '0';
if (i + k < n) s[i + k] = '0';
}
for (int i = 0; i < n; i++) { // проверка: пересчитываем v по s
bool one = (i - k >= 0 && s[i - k] == '1') || (i + k < n && s[i + k] == '1');
if ((v[i] == '1') != one) return "";
}
return s;
}4:10:51 Организация. После разбора три темы блока можно дорешивать в течение недели; запись занятия выложат как можно раньше, а разбор по этой теме будет через три недели. 4:12:38 Дедлайн — неделя после разбора. 4:13:36 Вопрос: нужно ли на туре доказывать жадный алгоритм? Лектор: если доказать быстрее, чем написать, — тогда да, но так бывает нечасто; жадные решения часто связаны с конструктивом и вырастают из «псевдодоказательства».
4:15:07 Что такое «конструктив». Сокращение от «конструктивное решение»: нужно предложить какое-нибудь подходящее решение, а не найти все. Например: «предложите тройку чисел, для которой $a^2+b^2=c^2$» — ответ $3,4,5$ достаточен, доказывать, что других нет, не требуется. Жадный алгоритм — когда вы придумываете идею и жадно набираете ответ; конструктивное решение — когда вы придумали идею и просто её реализуете, доказывая корректность.
4:16:16 Переход в другую параллель. Нужно написать преподавателям параллели, куда хочется перейти: они дают тест или просят решить определённое число задач.
4:16:54 Как стать призёром Всероса (заключительного этапа ВсОШ). Совет лектора: не нужно ничего «кардинально сложного» — верхняя граница — что-то вроде «до корнячка» (до корневой декомпозиции). Нужно огромное количество прорешанных задач: помогают Codeforces-раунды, дистанционные туры, а также умение не перегореть на самой олимпиаде. 4:17:35 Математика: нужна база до определённого уровня — например, на региональном этапе в одной задаче надо было знать дискриминант; сложные геометрические теоремы и малая теорема Ферма не обязательны, полезнее задачи на логику.
4:20:00 Сколько задач решать в день. Лектор советует решать раунды на Codeforces не ради подготовки, а ради удовольствия: так вы дольше сохраните интерес к олимпиадным задачам. 4:21:40 Можно ли решать вместе. Обсуждать идеи с другими слушателями можно и полезно, а вот вместе писать и скидывать код — нет.