0:27 Граф — это пара множеств $(V,E)$: $V$ — вершины, $E$ — рёбра. Проще всего представлять вершины точками на плоскости, а рёбра — отрезками (или любыми линиями), которые их соединяют. Дальше во всех примерах в графе $n$ вершин и $m$ рёбер.
1:19 Работать с графом «просто так» непонятно как. В коде можно хранить два множества прямо буквально: вектор вершин (их удобно пронумеровать числами $1,\dots,n$) и вектор пар — рёбер. Но это неудобно, поэтому разберём три стандартных способа.
2:15 Матрица смежности — это матрица $g$ размера $n\times n$, где $g[i][j]=1$ тогда и только тогда, когда есть ребро из $i$ в $j$ (иначе $0$).
g[i][j] = 1.g[i][j] = 0.g[v][u]. Можно хранить строки в bitset — тогда $O(n/64+\text{число соседей})$, но по сути всё равно порядка $n$.5:00 Это самый «базовый» способ хранения, и он не очень удобен на практике; осмысленный случай его применения всего один — о нём ниже, когда сравним способы.
9:33 Проблема матрицы — она хранит очень много нулей. Если вершин $10^5$, матрица $10^5\times10^5$ уже не поместится в память, а большая часть клеток в ней будет нулями. Список смежности хранит только реально существующее: это «список списков», то есть vector<vector<int>> g, где g[v] — все такие вершины $u$, что есть ребро из $v$ в $u$.
g[v].push_back(u) (в неориентированном графе ещё и g[u].push_back(v)). Обращение к списку по индексу работает за $O(1)$.11:14 Кратные рёбра — несколько рёбер между одной и той же парой вершин (дублёр дороги соединяет те же две точки). В ориентированном графе рёбра в противоположных направлениях кратными не считаются. Добавление за $O(1)$ допускает кратные рёбра; если их надо запрещать, придётся проверять, и тогда нужен set.
set, то $O(\log)$; unordered_set использовать не стоит — много памяти и работает не так быстро.12:43 Степень вершины $\deg v$ (от degree — «степень», «градус») — число соседей вершины.
13:52 В задачах обычно $n$ до $10^5$ и $m$ до $2\cdot10^5$ — для них идеален именно список смежности: почти всегда мы будем пользоваться vector<vector<int>> g, а добавление ребра — g[v].push_back(u).
14:31 Список рёбер — вектор пар $(u,v)$. Память $O(m)$, добавление ребра $O(1)$ (15:02 просто push_back), удаление $O(m)$ (или $O(1)$/$O(\log)$ при хранении в set), перебор соседей вершины $v$ — $O(m)$ (15:25 надо пройти по всем рёбрам и найти те, у которых есть $v$). 15:40 Это самый бесполезный способ; единственный алгоритм, где он реально нужен, — Краскал (его проходить будем позже).
| Матрица смежности | Список смежности | Список рёбер | |
|---|---|---|---|
| Память | $O(n^2)$ | $O(n+m)$ | $O(m)$ |
| Добавить ребро | $O(1)$ | $O(1)$ | $O(1)$ |
| Удалить ребро | $O(1)$ | $O(\deg v)$ (или $O(\log)$ с set) | $O(m)$ (или $O(\log)$ с set) |
| Перебрать соседей $v$ | $O(n)$ | $O(\deg v)$ | $O(m)$ |
16:15 Матрица смежности не зависит от числа рёбер — у неё всегда $n^2$ клеток. Поэтому, если $n$ порядка $1000$ и в графе может оказаться почти всё рёбер (полный граф), то $m$ всё равно порядка $n^2$, и можно просто завести матрицу и не задумываться: добавление и удаление рёбер бесплатны и без set. В графе на $10^5$ вершин и $2\cdot10^5$ рёбер матрица невозможна. Ещё матрица смежности естественна для алгоритма Флойда (его пока не проходили) и в теоретической информатике, где на граф удобно смотреть как на обычную матрицу. В остальных случаях — список смежности, «наш лучший друг».
20:31 Дальше рассматриваем только неориентированные графы. Связный граф — граф, в котором от любой вершины можно дойти до любой другой (возможно, проходя через другие). У дерева есть несколько определений, и все они на самом деле эквивалентны:
22:03 Задача — доказать, что это одно и то же. Для этого достаточно доказать четыре импликации по кругу: $1\Rightarrow2\Rightarrow3\Rightarrow4\Rightarrow1$ — тогда из любого определения следует любое другое.
$1\Rightarrow2$. 22:30 Дан связный граф без циклов, надо показать $m=n-1$. (23:01 Преподаватель поправила себя: в записи было «$n=m-1$», нужно именно $m=n-1$.) 24:04 Сначала: сколько рёбер нужно хотя бы, чтобы граф был связным? Для одной вершины — ноль, для двух — одно. Дальше по индукции: какие бы $n-1$ вершин мы ни взяли, чтобы их связать, нужно $n-2$ ребра, и ещё одно ребро нужно, чтобы присоединить оставшуюся вершину. 25:05 Цикла при этом не получается: цикл «потратил» бы $n$ рёбер на $n$ вершин, и на связывание всего остального графа рёбер уже не хватило бы. Это набросок; строгое доказательство — в блоке ниже.
$2\Rightarrow3$. 25:44 Дан связный граф с $m=n-1$. Докажем, что он ацикличен. 28:41 Предположим, что в нём есть цикл. Он «съедает» ребро: если убрать одно ребро цикла, граф останется связным, но рёбер станет $n-2<n-1$ — это противоречит Лемме А. (На лекции: «цикл потратил $n$ рёбер на $n$ вершин, и не хватит рёбер, чтобы присоединить остальные».) Значит циклов нет.
$3\Rightarrow4$. 29:03 Дан граф без циклов с $m=n-1$. Из ацикличности сразу следует, что между любыми двумя вершинами не больше одного пути (два разных пути дали бы цикл). 30:01 Осталось доказать связность. Пусть граф несвязен и состоит, скажем, из двух компонент размеров $x$ и $y$, $x+y=n$. Каждая из них связна и без циклов, поэтому по уже доказанному $1\Rightarrow2$ у неё $x-1$ и $y-1$ ребро, всего $n-2$, а должно быть $n-1$ — противоречие. (Для большего числа компонент рассуждение то же: рёбер получается $n-c$, где $c$ — число компонент, и $c=1$.) Значит граф связен, путь между любыми вершинами есть, и он единственный.
$4\Rightarrow1$. 31:09 Связность следует из того, что путь существует (буква $\exists$), а отсутствие циклов — из единственности пути (восклицательный знак): цикл дал бы две вершины, соединённые двумя разными путями.
31:38 Итак, $1\Rightarrow2$, $2\Rightarrow3$, $3\Rightarrow4$, $4\Rightarrow1$ — любое из определений можно получить из любого другого. Заметим, что ацикличность не означает связность: несколько не связанных между собой деревьев — ацикличный, но несвязный граф («шестой вид смешных графов», как сказала преподаватель), поэтому в определениях и нужны оба условия или условие $m=n-1$.
33:11 Лес — набор деревьев, не связанных друг с другом (как лес из отдельных деревьев): ацикличный граф, не обязательно связный.
34:08 Допустим, граф уже хранится списком смежности и вы хотите что-то с ним сделать: посчитать число компонент связности или, как сотрудник отдела навигации Яндекс.Карт, ходить по дорогам-графу. Для этого нужно научиться обходить граф. DFS (depth-first search) по-русски — обход в глубину (слово first куда-то теряется).
36:00 Выбираем стартовую вершину. Стоим в вершине и идём в самого левого ещё не посещённого сына (соседа), в нём делаем то же самое. Когда у вершины нет непокрашенных соседей, возвращаемся на уровень выше и идём в следующего соседа. 38:07 Если у вершины есть сосед, в котором мы уже были (покрашен), мы в него не идём — иначе мы бы ходили по циклу по кругу. Каждую вершину красим при входе и никогда не ходим в покрашенные — так мы гарантируем, что в каждой вершине побываем не больше одного раза.
Интерактив: ползунок или ▶ — по шагам, как DFS обходит граф (тот же, что на схеме ниже). Серая вершина — в неё вошли, но ещё не вышли; зелёная — обошли целиком.
39:35 Идея понятна: по сути алгоритм устроен как рекурсивный — вглубь, а когда некуда, поднимаемся по рекурсии наверх.
40:01 Есть два способа. Первый — рекурсивная функция (адекватный способ). Можно ещё писать рекурсивной лямбдой, но этим пока заниматься не нужно. Второй — самому имитировать рекурсию циклом со стеком: while, ручное добавление и удаление из стека. Преподаватель считает адекватным рекурсивный вариант; единственная проблема рекурсии, по её словам, — может закончиться стек вызовов, поэтому DFS на очень больших графах надо запускать с оглядкой.
41:02 Функция хранит текущую вершину $v$: сначала красим её (used[v] = comp: ненулевое значение значит «покрашена», а само число — номер компоненты), потом идём по всем соседям и, если сосед не покрашен, запускаем из него DFS — всего пять строк.
vector<vector<int>> g; // список смежности
vector<int> used; // 0 — не были, иначе — «покрашена»; здесь же храним номер компоненты
void dfs(int v, int comp) {
used[v] = comp; // красим вершину при входе
for (int u : g[v])
if (!used[u]) // в покрашенные не ходим
dfs(u, comp);
}
// число компонент связности и номер компоненты для каждой вершины
int components(int n) {
used.assign(n, 0);
int cnt = 0;
for (int v = 0; v < n; v++)
if (!used[v])
dfs(v, ++cnt); // каждый запуск обходит ровно одну компоненту
return cnt;
}42:08 Важный факт: DFS, запущенный из вершины $v$, обойдёт всю компоненту связности $v$ (гарантированно). Это то, что называют классом эквивалентности. Поэтому, чтобы посчитать число компонент, переберём вершины: если вершина не покрашена, запускаем из неё DFS и увеличиваем счётчик.
42:50 Чтобы найти сами компоненты, а не только их число, вместо bool удобно хранить в массиве used номер компоненты: ноль означает «ещё не были», а положительное число — номер компоненты, к которой относится вершина (так и сделано в коде выше). Второй вариант — складывать вершины в вектор по ходу обхода (в начале DFS делать comp.push_back(v)), не забывая очищать его перед следующей компонентой.
44:05 DFS по всему графу работает за $O(n+m)$: в каждой вершине он побывает один раз, а на каждое ребро посмотрит по два раза — с одной и с другой стороны. Внешний цикл по вершинам даёт ещё $O(n)$. Эту оценку важно помнить: типичная ошибка — назвать другую асимптотику.
46:04 Дальше лекцию продолжил второй преподаватель. Двудольный граф — это разбиение вершин на два множества так, что рёбра есть только между долями. Хочется проверять двудольность с помощью DFS.
46:52 Заметим: если убрать рёбра между долями, получится две «компоненты», в каждой из которых все вершины можно покрасить в один цвет, и рёбер между одноцветными вершинами не бывает. Поэтому будем красить граф в два цвета: запустим DFS из какой-нибудь вершины и покрасим её в цвет $1$, всех её соседей — в цвет $2$, их соседей снова в цвет $1$, и так далее, пока есть куда идти. Если удалось предъявить такую раскраску, граф двудольный.
48:10 Что, если мы стоим в вершине и видим ребро в вершину, уже покрашенную тем же цветом, что и текущая? Это значит, что раскраска не получается — граф не двудольный: мы пришли из вершины цвета $2$, так что текущая должна быть цвета $1$, а теперь видим ребро между «первым и первым».
49:03 Остаётся научиться красить аккуратно. Стандартный приём: цвет соседа — это $3-c$ (если $c=1$, то $2$; если $c=2$, то $1$), поэтому «переключение» цвета — одна формула. 49:52 Изначально у всех вершин цвет $0$ (не покрашены), а стартовую вершину красим в цвет $1$.
vector<vector<int>> g;
vector<int> color; // 0 — не покрашена, 1 и 2 — доли
bool bad;
void dfsColor(int v, int c) {
color[v] = c;
for (int u : g[v]) {
if (color[u] == 0) dfsColor(u, 3 - c); // 3 - 1 = 2, 3 - 2 = 1
else if (color[u] == c) bad = true; // ребро между одноцветными вершинами
}
}
bool isBipartite(int n) {
color.assign(n, 0);
bad = false;
for (int v = 0; v < n; v++) // граф может быть несвязным
if (color[v] == 0) dfsColor(v, 1);
return !bad;
}50:37 Нужно пройтись по всем вершинам, потому что граф может быть несвязным: в каждой компоненте запускаем DFS отдельно. 51:13 Двудольный граф вполне может быть несвязным: в каждой компоненте чередование цветов можно выбрать любым из двух способов (например, поменять цвета местами), и в разных компонентах это независимо. Поэтому и разбиение на доли для несвязного графа неединственно.
53:34 Почему именно такой алгоритм? Если вершину покрасили в первый цвет (отнесли в левую долю), то все её соседи обязательно должны быть в правой доле. Если же при обходе мы позднее пришли к ней с ребром от вершины того же цвета, то раскраска ломается — граф не двудольный.
54:47 DFS строит дерево: если оставить только рёбра, по которым мы реально прошли, то мы никогда не заходили в уже посещённую вершину, поэтому циклов нет. Такие рёбра называются древесными. 55:52 Остальные рёбра, на которые DFS посмотрел, но не пошёл по ним, называются обратными (в неориентированном графе — рёбра «наверх», к предку). Далее нужно уметь искать циклы.
57:36 Любой цикл устроен так: мы спускаемся по древесным рёбрам, а потом находим обратное, которое замыкает цикл. Нужно уметь его найти.
58:03 Для этого запоминаем для каждой вершины предка по обходу: par[v]. Когда в вершине $v$ находим обратное ребро в $u$, поднимаемся по предкам от $v$, добавляя вершины в список, пока не дойдём до $u$. Эти вершины и есть цикл. 59:15 Это поиск цикла в любом графе (дерево здесь возникает только потому, что DFS его строит); если в графе несколько циклов, найдём какой-то один.
61:06 Исправление, сделанное по ходу: цикл «поднимаемся, пока $v\ne u$» не добавляет саму конечную вершину $u$ — её нужно добавить в конце отдельно (push_back(u)). 61:42 Восстановление работает за длину цикла: подъёмов ровно столько, сколько вершин в цикле.
62:25 Вызывать getCycle нужно внутри DFS: когда мы перебираем соседей, непокрашенный сосед даёт очередное древесное ребро, а в ветке «иначе» сосед уже посещён — значит, это обратное ребро, и из него надо вызвать getCycle(v, u).
p, и ребро обратно в него пропускается: без этого каждое ребро $v$–предок принималось бы за «обратное» и цикл «находился» бы в любом графе с рёбрами. Этот приём на лекции отдельно не проговаривался, но он нужен для корректности.vector<vector<int>> g;
vector<int> used, par;
vector<int> cyc; // найденный цикл
// подъём по предкам от v до u: вершины цикла
vector<int> getCycle(int v, int u) {
vector<int> res;
for (int x = v; x != u; x = par[x]) res.push_back(x);
res.push_back(u); // саму конечную вершину тоже добавляем
return res;
}
bool dfsCycle(int v, int p) { // p — предок v в обходе
used[v] = 1;
for (int u : g[v]) {
if (u == p) continue; // ребро назад по дереву — не цикл
if (!used[u]) {
par[u] = v; // древесное ребро
if (dfsCycle(u, v)) return true;
} else { // уже были в u, и это не предок по ребру → обратное ребро
cyc = getCycle(v, u);
return true;
}
}
return false;
}
bool findCycleUndirected(int n) {
used.assign(n, 0); par.assign(n, -1);
for (int v = 0; v < n; v++)
if (!used[v] && dfsCycle(v, -1)) return true;
return false;
}u == p — пропускаем» считает ребро в предка единственным. Если в графе возможны кратные рёбра, то вторая копия ребра $v$–$p$ — это уже настоящий цикл длины $2$, и пропускать нужно по номеру ребра, а не по вершине. Кроме того, из недвойного обхода мы находим цикл первым же обратным ребром — для этого нам важно останавливаться сразу (return true).65:54 В ориентированном графе древесные и обратные рёбра становятся ориентированными. Добавляются ещё два типа:
68:37 Почему не бывает перекрёстного «слева направо»: если бы такое ребро было, то, дойдя до его начала, мы бы увидели, что другой конец ещё не посещён, и пошли бы по нему — ребро стало бы древесным (а часть дерева «перестроилась» бы).
70:04 В неориентированном графе прямые рёбра вводить нет смысла: прямое и обратное — это одно и то же ребро, просто увиденное с разных концов. Перекрёстных там тоже не бывает — любое такое ребро DFS превратил бы в древесное.
71:06 Если есть обратное ребро, цикл найти можно. Могут ли в образовании цикла участвовать другие рёбра? 71:44 Разобрали прямые и перекрёстные рёбра: прямое ребро ведёт в уже полностью обойдённое поддерево, и чтобы вернуться назад, всё равно нужны другие рёбра; перекрёстное ведёт в поддерево, которое уже обработано целиком, а цикл означал бы возвращение в вершину, обход которой ещё не закончен. 74:46 Поэтому нас интересует самый простой цикл — тот, в котором меньше всего различных типов рёбер: цикл из древесных и одного обратного рёбер. Прямые и перекрёстные рёбра для поиска циклов не нужны.
75:03 Чтобы отличать, где мы находимся, красим вершины не в два, а в три цвета: $0$ — не посещали; $1$ — вошли, но ещё не вышли (рассматриваем всё, что достижимо из неё); $2$ — посетили и полностью вышли. 76:28 На картинке цикла все его вершины имеют цвет $1$, а ребро, замыкающее цикл, — обратное.
76:59 DFS: заходим в вершину, красим её в $1$, перебираем рёбра. Если сосед не посещён — идём в него. 77:54 Иначе, если мы видим сосед цвета $1$ (вошли, но не вышли) — это цикл. Дальше можно делать то, что требует задача, например вызвать getCycle, чуть-чуть модифицировав: мы поднимаемся вверх по предкам и добавляем вершины в обратном порядке, поэтому в конце нужен reverse, чтобы вершины шли в том порядке, в каком рёбра даны в графе. 79:36 В конце, когда перебрали все рёбра и все рекурсивные вызовы закончились, красим вершину в цвет $2$ — из неё больше некуда идти.
vector<vector<int>> g; // ориентированные рёбра v -> u
vector<int> color, par; // 0 — не были, 1 — вошли, но не вышли, 2 — вышли
vector<int> cyc;
bool dfsCycleDir(int v) {
color[v] = 1;
for (int u : g[v]) {
if (color[u] == 0) {
par[u] = v;
if (dfsCycleDir(u)) return true;
} else if (color[u] == 1) { // ребро в вершину, из которой ещё не вышли → цикл
cyc.clear();
for (int x = v; x != u; x = par[x]) cyc.push_back(x);
cyc.push_back(u);
reverse(cyc.begin(), cyc.end()); // порядок вдоль рёбер: u -> ... -> v -> u
return true;
}
}
color[v] = 2; // обошли всё, что достижимо из v
return false;
}
bool findCycleDirected(int n) {
color.assign(n, 0); par.assign(n, -1);
for (int v = 0; v < n; v++)
if (color[v] == 0 && dfsCycleDir(v)) return true;
return false;
}80:27 Как работает getCycle: так же, как в неориентированном случае, только порядок вершин разворачиваем. Предка надо заполнять в DFS: после par[u] = v перед рекурсивным вызовом. 82:21 Напомним смысл цветов: цвет $1$ — вошли в вершину, и в ней ещё есть недообойдённое; когда все рекурсивные вызовы закончились и перебраны все рёбра, красим в $2$.
83:49 Двудольность мы определили через раскраску в два цвета. Как сформулировать её на языке циклов?
Теорема. Граф двудольный тогда и только тогда, когда все его циклы имеют чётную длину (то есть в нём нет циклов нечётной длины).
$\Rightarrow$ 85:05 Рассмотрим любой цикл. Каждое ребро идёт из одной доли в другую (внутри доли рёбер нет), поэтому вершины чередуются: левая, правая, левая… Чтобы вернуться в исходную вершину, нужно сделать чётное число шагов — длина цикла чётна.
$\Leftarrow$ 86:31 Более «мерзкое» доказательство. Считаем граф связным (для каждой компоненты делаем то же). Запустим обход из вершины $s$ и разобьём вершины на два множества: $U_1$ — вершины, у которых расстояние от $s$ чётно, и $U_2$ — с нечётным. Докажем, что внутри $U_1$ и внутри $U_2$ нет рёбер. 88:45 Пусть есть ребро между вершинами $x$ и $y$ из одного множества. Рассмотрим кратчайшие пути из $s$ в $x$ и в $y$ и это ребро. 89:17 Если оба расстояния чётные ($2k$ и $2m$), то замкнутый путь $s\to x\to y\to s$ имеет длину $2k+1+2m$ — нечётную. Если оба нечётные ($2k+1$ и $2m+1$), то длина $2k+1+1+2m+1=2k+2m+3$ — тоже нечётная. Получили нечётный цикл — противоречие.
90:11 Практический вывод: когда в задаче что-то говорят про двудольность, можно думать, что все циклы чётной длины, и использовать это; а если в таблице баллов написано «все циклы чётной длины», надо сразу понимать, что граф двудольный и красится в два цвета.
91:37 Дан ориентированный граф. Нужно перенумеровать вершины, поставив каждой порядковый номер, так, чтобы для каждого ребра $v\to u$ номер $v$ был меньше номера $u$ (то есть «все рёбра ведут слева направо»). Это и есть топологическая сортировка («топсорт»).
92:46 На каких графах нельзя? На неориентированных вопрос не ставим вообще. А ещё нельзя на графах с циклом: для цикла $a_1\to a_2\to\dots\to a_k\to a_1$ из условия получается $a_1<a_2<\dots<a_k<a_1$ — невозможно. Значит, топсорт существует только для ориентированных ациклических графов (DAG).
94:47 Посмотрим на «последнюю» вершину: из неё никуда не ведут рёбра. Ей можно дать самый большой номер без проблем — какие бы рёбра в неё ни входили, у их начал номер будет меньше. 95:52 Дальше берём вершину, у которой нет рёбер в вершины, которым номер ещё не присвоен, и даём ей следующий по убыванию номер; и так, пока всем не выдадим номера. Почему такая процедура даёт корректный порядок — понятно: каждая вершина получает номер больше, чем номера всех, в кого из неё ведут рёбра.
97:33 Если «листьев» (вершин без исходящих рёбер) несколько, неважно, который брать: для любого листа это верно — его можно поставить последним.
98:55 Идея реализации: не нужно ничего удалять из графа (никаких remove и т. п.). Идём DFS: когда мы закончили обработку вершины (обработали всё её поддерево), ей можно выдать очередной номер — все, в кого из неё ведут рёбра, уже получили номера. То есть вершина добавляется в список после просмотра всех её потомков (в момент выхода). 101:11 Уточнение к вопросу из зала: сначала идём вглубь до вершины без исходящих рёбер, заносим её и поднимаемся до вершины, из которой можно идти дальше вниз, и так далее; всё это делает сам DFS.
104:06 Вместо вектора можно было бы вести глобальный счётчик и выдавать номера, а потом ещё сортировать — но зачем, если можно проще. 105:07 Ещё один нюанс: в конце получается порядок «справа налево» (рёбра ведут справа налево), а нужно слева направо, поэтому список выхода разворачиваем — это одна строчка. 105:36 И DFS нужно запускать из всех непокрашенных вершин, а не только из нулевой — иначе получится не весь топсорт.
vector<vector<int>> g; // ориентированный ациклический граф
vector<int> used, order_; // order_ — вершины в порядке выхода из dfs
void dfsTop(int v) {
used[v] = 1;
for (int u : g[v])
if (!used[u]) dfsTop(u);
order_.push_back(v); // вышли из v: все её потомки уже в списке
}
vector<int> topSort(int n) {
used.assign(n, 0); order_.clear();
for (int v = 0; v < n; v++) // обязательно запускаем из всех вершин
if (!used[v]) dfsTop(v);
reverse(order_.begin(), order_.end()); // рёбра должны вести слева направо
return order_;
}106:29 Зачем это нужно. В дальнейшем топсорт пригодится для поиска компонент сильной связности, для динамического программирования на ациклических графах (порядок пересчёта значений задаёт именно топсорт), для 2-SAT — подробнее, когда дойдём до динамики.
108:13 Дано дерево; нужно найти его диаметр — максимум расстояний по всем парам вершин. (Расстояние — число рёбер на единственном пути; на взвешенном графе упражнение будет позже: алгоритм работает так же.) Решение «за $N^2$» очевидно: из каждой вершины запустить DFS и обновлять ответ.
109:40 Неверная идея из зала: взять какой-то корень, найти самую глубокую вершину, затем вторую самую глубокую из других веток корня и сложить. Контрпример: диаметр может не проходить через выбранный корень, поэтому две самые глубокие ветки от корня могут дать меньше диаметра.
112:07 Идеи из зала: диаметр можно найти одним DFS — для каждой вершины запоминать глубину самого глубокого потомка и складывать две наибольшие глубины среди детей (как раз путь «вверх, потом вниз» через вершину $l$). Преподаватель согласилась, что это верно, но сказала, что это уже динамика на деревьях, и обсудим её на занятии по динамике.
114:48 «Смешные факты»: у дерева может быть несколько диаметров, но все они пересекаются в одной точке — центре (середине). Пусть центр — вершина (если центр — ребро, доказательство такое же, но «чуть более мерзкое»). Если бы два диаметра не пересекались, соединим их центры путём положительной длины — тогда получился бы путь длиннее диаметра. Если они пересекаются, но не в центре, рассуждение аналогично: перебираем куски от концов до центров и находим путь длиннее.
119:45 Преподаватель предупредила, что не любит это доказательство. Его схема на лекции: пусть $x,y$ — истинный диаметр, $s$ — корень, первый DFS вернул $v$. Любой путь в корневом дереве — это путь вверх, а потом вниз; пусть $x\to l\to y$, где $l$ — вершина, через которую путь «перегибается». Рассматриваются два случая: $v$ лежит в поддереве $l$ или нет. В каждом оценивается расстояние от $v$ до $y$ (или $x$) через длины кусков пути и показывается, что оно не меньше $d(x,y)$ — иначе противоречие с тем, что $x,y$ диаметр. Затем показывается, что второй DFS из $v$ находит вершину $u$, для которой $d(v,u)$ — диаметр: $u$ — лист (иначе можно продлить), а все остальные расстояния из $v$ не больше.
134:26 Как найти самую глубокую вершину: считаем в DFS глубину dep[v] = dep[par] + 1 и запоминаем вершину с максимальной глубиной. Перед вторым запуском массив глубин нужно обнулить. Следите за корнем: для корня предка нет, и если передать -1 как индекс в массив, C++ вам этого не простит. 135:23 Вопрос: будет ли работать, если взять не «висящую» вершину, а произвольную? Да, будет: конец первого DFS окажется листом, а второго — листом на другом конце.
vector<vector<int>> g; // дерево
vector<int> dep, par;
void dfsDepth(int v, int p) {
par[v] = p;
for (int u : g[v])
if (u != p) {
dep[u] = dep[v] + 1; // глубина = глубина предка + 1
dfsDepth(u, v);
}
}
// возвращает самую глубокую вершину при запуске из s
int farthest(int n, int s) {
dep.assign(n, 0); par.assign(n, -1);
dfsDepth(s, -1);
return max_element(dep.begin(), dep.end()) - dep.begin();
}
// диаметр (число рёбер) и его концы
int diameter(int n, int &x, int &y) {
x = farthest(n, 0); // первый обход — из любой вершины
y = farthest(n, x); // второй — из самой глубокой
return dep[y];
}137:29 После перерыва — разбор контеста по бинарному поиску, который не успели разобрать на прошлой неделе. Обязательные задачи можно решать и после просмотра разбора.
138:01 Задача A («Коровы») разбиралась на лекции — если непонятно, пересмотрите. 138:50 Задача B — вычисление квадратного корня: бинарный поиск по действительным числам; ровно такая же функция разбиралась на лекции — просто написать бинпоиск по ответу с фиксированным числом итераций.
139:15 Есть партии, у $i$-й партии планируют проголосовать $a_i$ человек. Нужно подкупить руководителя какой-то партии и сделать так, чтобы она победила (получила строго больше голосов, чем каждая другая партия), потратив как можно меньше денег. Стоимость в разборе: подкуп руководителя стоит $c_i$, и ещё по единице денег за каждый голос, который переходит от одной партии к другой — то есть $c_i+(\text{число переведённых голосов})$.
139:49 Переберём, кого делаем победителем ($i$). Тогда нужно узнать, сколько голосов надо «купить» (перетащить от остальных). 141:01 Бинарный поиск по итоговому числу голосов $M$ победителя. «Оракул» говорит, что победа достижима при $M$ голосах; проверяем. Если у победителя будет $M$ голосов, то у всех остальных должно быть не больше $M-1$; значит, у партий с $a_j>M-1$ нужно отнять $\sum_{j\ne i}\max(0,\,a_j-(M-1))$ голосов. Эти голоса мы забираем себе: их должно быть не больше, чем мы докупаем, то есть не больше $M-a_i$. 141:48 Условие проверки: $\sum_{j\ne i}\max(0,\,a_j-M+1)\le M-a_i$. Ясно, что перекупать голоса на «не нашего» кандидата невыгодно.
144:02 Чем больше $M$, тем меньше нужно отнимать и тем больше мы можем докупить, поэтому проверка монотонна — подходит бинарный поиск по $M$.
146:02 Если на каждую проверку тратить $O(n)$, то получится $O(n)$ на проверку, $\log$ на бинпоиск и $n$ кандидатов — слишком долго. Поэтому отсортируем массив один раз за $O(n\log n)$ (сами $a_j$ не меняются). Тогда все «лишние» голоса — это суффикс отсортированного массива: находим lower_bound первого $a_j\ge M$ и считаем сумму суффикса: $\sum_{j\ge k}a_j-(n-k)(M-1)$ — «суффиксная сумма» и значение $M-1$ для каждой из $n-k$ партий. Собственный вклад победителя нужно вычесть, если $a_i\ge M$.
147:24 Вопрос из зала: почему не покупать всегда партию с самым выгодным отношением цены к числу голосов? Потому что заранее непонятно, с каким итоговым числом голосов мы победим: можно купить очень дёшево партию, у которой совсем мало голосов, и нужные для победы голоса возьмутся у других партий — этот эффект нельзя предсказать формулой. Поэтому нужен бинарный поиск по числу голосов.
149:57 Итого для каждого кандидата $O(\log C\cdot\log n)$ (бинпоиск по $M$ и lower_bound внутри проверки), а всего — $O(n\log C\log n)$.
// a[i] — за сколько голосов планирует проголосовать i-я партия.
// need[i] — сколько голосов минимум нужно «купить» (перетащить от остальных), чтобы партия i победила строго.
// Полная стоимость для партии i в задаче — c[i] (подкуп руководителя) + need[i]; ответ — минимум по i.
vector<long long> votesToBuy(const vector<long long>& a0) {
int n = a0.size();
vector<long long> a = a0;
sort(a.begin(), a.end());
vector<long long> suf(n + 1, 0); // suf[k] = a[k] + ... + a[n-1]
for (int k = n - 1; k >= 0; k--) suf[k] = suf[k + 1] + a[k];
long long total = suf[0];
vector<long long> need(n);
for (int i = 0; i < n; i++) { // перебираем будущего победителя (индекс в отсортированном массиве)
// можно ли выиграть, имея в итоге M голосов?
auto ok = [&](long long M) {
int k = lower_bound(a.begin(), a.end(), M) - a.begin(); // у a[k..] голосов >= M — их придётся урезать
long long cut = suf[k] - (long long)(n - k) * (M - 1); // лишние голоса, если все должны стать <= M-1
if (a[i] >= M) cut -= a[i] - (M - 1); // сама партия i среди «остальных» не считается
return cut <= M - a[i]; // отнять нужно не больше, чем мы докупаем
};
long long lo = a[i] - 1, hi = total; // lo — «нельзя», hi — «можно» (M = total годится всегда)
while (hi - lo > 1) {
long long mid = (lo + hi) / 2;
if (ok(mid)) hi = mid; else lo = mid;
}
need[i] = hi - a[i]; // докупаем M - a[i] голосов
}
// need посчитан для отсортированного массива; раскладываем обратно по исходным номерам
vector<int> idx(n); iota(idx.begin(), idx.end(), 0);
stable_sort(idx.begin(), idx.end(), [&](int x, int y) { return a0[x] < a0[y]; });
vector<long long> res(n);
for (int p = 0; p < n; p++) res[idx[p]] = need[p];
return res;
}152:00 Дан массив из нулей и единиц, про который известно, что первый элемент — $1$, последний — $0$. Нужно найти два подряд идущих элемента «$1$, $0$». 152:14 Это ровно тот же инвариант, о котором на лекции по бинпоиску говорили «безумное количество раз»: $a_l=1$, $a_r=0$. Спрашиваем средний элемент: единичка — двигаем $l$, иначе $r$. Когда $r=l+1$, указатели стоят ровно на двух подряд идущих элементах «$1,0$».
// a[0] = 1, a[n-1] = 0. Найти i, что a[i] = 1 и a[i+1] = 0
int findOneZero(const vector<int>& a) {
int l = 0, r = a.size() - 1; // инвариант: a[l] = 1, a[r] = 0
while (r - l > 1) {
int m = (l + r) / 2;
if (a[m] == 1) l = m; // единичка — двигаем левую границу
else r = m; // нолик — правую
}
return l; // r = l + 1
}154:06 Даны массивы (и запросы к ним): есть возрастающий массив $A$ и убывающий массив $B$; нужно найти такой индекс $k$, что $\max(A_k,B_k)$ как можно меньше. 154:56 Нарисуем: $A$ растёт, $B$ убывает; максимум из двух — это «верхняя огибающая» (сначала убывающая функция $B$, потом после точки пересечения возрастающая $A$). Нас интересует просто место пересечения — его ищем бинпоиском. 156:17 Два инварианта: слева от пересечения $A_k<B_k$, а справа $A_k\ge B_k$. Ответ — либо первый индекс справа от пересечения, либо последний слева — выбираем лучший из двух.
// A возрастает, B убывает; ищем индекс k, при котором max(A[k], B[k]) минимален
int bestIndex(const vector<int>& A, const vector<int>& B) {
int n = A.size();
int lo = -1, hi = n; // для k <= lo: A[k] < B[k]; для k >= hi: A[k] >= B[k]
while (hi - lo > 1) {
int mid = (lo + hi) / 2;
if (A[mid] < B[mid]) lo = mid; else hi = mid;
}
// минимум — рядом с местом пересечения: либо hi, либо hi - 1
int best = -1;
for (int k : {hi - 1, hi})
if (k >= 0 && k < n && (best < 0 || max(A[k], B[k]) < max(A[best], B[best]))) best = k;
return best;
}157:03 Здесь не нужен бинпоиск. Дан массив $a$ из $n$ элементов; функция $f(p)$ — это (количество индексов $i<p$ с $a_i=a_p$) умножить на (количество индексов $j>p$ с $a_j\ne a_p$). «Количество людей слева того же роста, что и вы, умножить на количество людей справа с неравным ростом». В разборе берётся лучшее (наибольшее) значение $f$.
158:22 Левую часть посчитать просто (сколько равных уже встречали), а правую — через общий размер: справа от позиции $p$ всего $n-1-p$ элементов, из них равных $a_p$ — столько, сколько всего равных минус «слева» минус сам элемент. 160:05 Пример из лекции: массив $2,1,3,3,4,1,2,5$ (индексы $0..7$): двойка стоит на позициях $0$ и $6$, единица — на $1$ и $5$, тройка — на $2$ и $3$, четвёрка на $4$, пятёрка на $7$. Для $p=3$ (вторая тройка): слева одна тройка, справа четыре элемента и ни один не равен тройке — $1\cdot4=4$. Это и есть наибольшее значение $f$ в этом массиве. 162:43 На лекции разложили индексы по значениям и считали формулу, перебирая для каждого значения его позиции по возрастанию; в коде ниже то же самое делается одним проходом со счётчиками.
// f(p) = (сколько i < p с a[i] = a[p]) * (сколько j > p с a[j] != a[p]); возвращаем максимум f(p)
long long bestF(const vector<int>& a) {
int n = a.size();
map<int,int> total, seen;
for (int x : a) total[x]++;
long long best = 0;
for (int p = 0; p < n; p++) {
long long left = seen[a[p]]; // равных слева
long long rightEq = total[a[p]] - left - 1; // равных справа
long long rightNe = (n - 1 - p) - rightEq; // справа всего n-1-p, из них не таких, как a[p]
best = max(best, left * rightNe);
seen[a[p]]++;
}
return best;
}166:45 Два принтера; один делает лист за $x$ секунд, второй — за $y$ секунд. Есть один оригинал, нужно сделать $n$ копий. За какое минимальное время можно? 167:25 Переберём время $T$. Сначала нужно откопировать оригинал на одном из принтеров — быстрейшем, это $\min(x,y)$ секунд. После этого у нас два листа, и оба принтера могут работать. 167:51 На оставшееся время $T-\min(x,y)$ первый принтер сделает $\left\lfloor\frac{T-\min(x,y)}{x}\right\rfloor$ копий, второй $\left\lfloor\frac{T-\min(x,y)}{y}\right\rfloor$, плюс одна уже сделанная первая копия. Если копий хватает — пробуем меньшее время, иначе большее. Задача очень лёгкая.
// минимальное время, за которое два принтера (x и y секунд на лист) сделают n копий
long long minTime(long long n, long long x, long long y) {
long long t0 = min(x, y); // первую копию можно сделать только на одном принтере
long long lo = 0, hi = t0 * n; // hi заведомо хватает
while (hi - lo > 1) {
long long T = (lo + hi) / 2;
long long copies = (T < t0) ? 0 : 1 + (T - t0) / x + (T - t0) / y;
if (copies >= n) hi = T; else lo = T;
}
return hi;
}Пример (собственный): $n=4$, $x=1$, $y=2$: за $3$ секунды первый принтер делает копии в моменты $1,2,3$ — три, второй (начав в момент $1$) — одну в момент $3$, итого $4$; за $2$ секунды получается только $2+0=2$. Ответ $3$.
168:54 Есть провода длин $a_i$; нужно получить хотя бы $k$ одинаковых по длине кусков, и длину куска сделать как можно больше. Переберём длину $L$: из $i$-го провода получится $\lfloor a_i/L\rfloor$ кусков. Если сумма $\ge k$, то можно попробовать длину больше (двигаем $l$), иначе — меньше. 169:15 Ответ ноль, если даже длиной $1$ не набирается $k$ кусков, то есть сумма $a_i$ меньше $k$.
// из проводов a[i] нужно получить k кусков одинаковой целой длины; максимальная длина куска (0, если нельзя)
long long maxPiece(const vector<long long>& a, long long k) {
long long lo = 0, hi = *max_element(a.begin(), a.end()) + 1; // lo — можно (0 всегда), hi — нельзя
while (hi - lo > 1) {
long long L = (lo + hi) / 2;
long long cnt = 0;
for (long long x : a) cnt += x / L; // сколько кусков длины L из каждого
if (cnt >= k) lo = L; else hi = L;
}
return lo;
}170:26 Эта задача очень похожа на «Дипломы», которую разбирали раньше. Переберём ширину $d$ защитной полосы вокруг каждого прямоугольника $a\times b$. Тогда на листе $W\times H$ по горизонтали поместится $\lfloor W/(a+2d)\rfloor$ штук, по вертикали $\lfloor H/(b+2d)\rfloor$, всего их произведение. Если получилось достаточно — $d$ можно увеличивать, иначе уменьшать. Из-за ограничений на значения нужно быть аккуратными с переполнением и границами бинпоиска.
// на листе W×H раскладываем n прямоугольников a×b, каждый в рамке толщиной d со всех сторон;
// максимальное целое d (или -1, если нельзя даже при d = 0)
long long maxFrame(long long W, long long H, long long a, long long b, long long n) {
auto fits = [&](long long d) {
long long cx = W / (a + 2 * d), cy = H / (b + 2 * d); // сколько помещается по горизонтали и вертикали
return cx * cy >= n;
};
if (!fits(0)) return -1;
long long lo = 0, hi = min(W, H) + 1; // hi — заведомо много (рамка не больше листа)
while (hi - lo > 1) {
long long mid = (lo + hi) / 2;
if (fits(mid)) lo = mid; else hi = mid;
}
return lo;
}172:11 Нужно срубить все деревья (количество $X$) и за минимальное число дней. Пусть мы уложимся в $T$ дней. Каждый работник рубит свои $A$ деревьев в день, но каждый $K$-й день отдыхает; за $T$ дней у него $T-\lfloor T/K\rfloor$ рабочих дней, и он срубит $A\cdot(T-\lfloor T/K\rfloor)$ деревьев — второй работник считается аналогично. Если сумма больше либо равна $X$, то время можно уменьшать ($r=T$), иначе увеличивать. Всё достаточно просто (параметры второго работника в разборе подробно не называли).
173:51 Есть предметы со стоимостью $v_i$ и весом $w_i$ (положительные). Нужно выбрать ровно $k$ предметов так, чтобы $\dfrac{\sum v}{\sum w}$ было как можно больше. Жадности здесь не работают. 174:27 Бинпоиск по ответу. Пусть ответ не меньше $r$. Раз все веса положительные, неравенство $\sum v\ge r\sum w$ можно переписать как $\sum (v_i-r\,w_i)\ge0$ — по одному и тому же подмножеству. Для проверки заводим массив $t_i=v_i-r\,w_i$, сортируем (или берём $k$ наибольших) и смотрим, неотрицательна ли сумма $k$ максимальных. Если да — ответ ещё больше ($l=r$), иначе меньше. 177:25 Сложность: $\log$ числа итераций умножить на $O(n\log n)$ сортировки; можно ускорить функцией nth_element, которая ставит $k$-й элемент на своё место (слева все не больше, справа все не меньше) за $O(n)$ — итого $O(n\log C)$.
// выбрать ровно k предметов (стоимость v[i], вес w[i] > 0) так, чтобы sum(v) / sum(w) было максимальным
double bestRatio(const vector<double>& v, const vector<double>& w, int k) {
int n = v.size();
double lo = 0, hi = 1e9; // ответ лежит в [lo, hi]
for (int it = 0; it < 100; it++) {
double r = (lo + hi) / 2; // проверяем: можно ли получить отношение >= r
vector<double> t(n);
for (int i = 0; i < n; i++) t[i] = v[i] - r * w[i]; // sum(v) >= r * sum(w) <=> sum(v - r*w) >= 0
nth_element(t.begin(), t.begin() + (k - 1), t.end(), greater<double>()); // k наибольших — в начале
double s = 0;
for (int i = 0; i < k; i++) s += t[i];
if (s >= 0) lo = r; else hi = r;
}
return lo;
}180:10 Массив отсортирован, каждое число в нём встречается дважды, и только число $x$ — один раз. Нужно найти $x$. 180:45 Расставим индексы $0,1,2,\dots$: до числа $x$ пары стоят на позициях «чётная–нечётная» ($0$–$1$, $2$–$3$, …), а после $x$ чётность сломана: пары «нечётная–чётная». Поэтому перебираем пару $(2m,2m+1)$ и спрашиваем: a[2m] == a[2m+1]? Если равны — мы до $x$, иначе — после. Так мы перебираем только половину позиций, и не нужно думать, какие именно два элемента сравнивать.
// отсортированный массив, каждое число встречается дважды, кроме одного; находим одиночное
int lonely(const vector<int>& a) {
int n = a.size(); // n нечётно
int lo = -1, hi = n / 2; // пары (2i, 2i+1): для i <= lo они равны, для i >= hi — уже сломаны
// инвариант: слева от одиночного a[2i] == a[2i+1]
while (hi - lo > 1) {
int mid = (lo + hi) / 2;
if (a[2 * mid] == a[2 * mid + 1]) lo = mid; else hi = mid;
}
return a[2 * hi]; // первая «сломанная» пара начинается с одиночного числа
}184:28 По кругу расположены комнаты, в каждой горит свет или нет; мы стоим в одной из них и хотим узнать, сколько комнат в круге (длину цикла). Умеем ходить на соседнюю комнату вправо или влево, смотреть и менять лампочку в текущей комнате.
184:55 Идея: удваивающиеся шаги. Для $L=1,2,4,8,\dots$: идём вправо на $L$ шагов, гася свет в каждой комнате; в последней зажигаем свет; затем идём обратно влево, пока не встретим свет или не сделаем $L$ шагов. 188:10 Если свет встретили на шаге $c$, то это та самая лампа, которую мы зажгли, и круг замкнулся за $c$ шагов — длина цикла равна $c$. Если света не встретили, то круг больше $L$ (мы дошли до стартовой комнаты и не вернулись по кругу), и повторяем с удвоенным $L$.
189:42 Пример с лекции: пять комнат, где-то горит свет. Шаг $4$: идём вправо, гася свет, и в последней (пятой) комнате зажигаем свет; возвращаемся обратно на пять позиций — 190:45 мы смогли пройти дальше и не встретили свет, значит, круг больше. Шаг $8$: идём вправо, гася всё по пути, — мы обошли круг больше раза; в последней комнате зажигаем свет и идём обратно: встречаем свет раньше, чем сделаем все шаги. 191:46 Тогда мы знаем верхнюю оценку на длину пути, а плюс к этому у нас горит ровно одна лампа (всё остальное по пути потушено), и остаётся только измерить круг. (Собственная проверка для $n=5$ по коду ниже: $L=4$ — света не нашли; $L=8$ — идём вправо на $8$ шагов, кончаем в комнате с номером $8\bmod5=3$, зажигаем лампу, и после $5$ шагов влево снова оказываемся в ней — длина круга $5$.)
192:18 Преподаватель обсуждала, что при возврате надо шагать на $2^k$ плюс один–два шага, чтобы случайно не пропустить ответ $2^k$. 193:52 Вопрос слушателя: «бинпоиск тут используется?» Ответ: нет — тут идея итерирования по степеням двойки (по сути, галопирующий поиск): пока не нашли, увеличиваем шаг вдвое.
// по кругу n комнат, в каждой лампа горит или нет; мы стоим в одной из них и n не знаем.
// Умеем: идти на комнату вправо/влево, видеть и менять лампу в текущей комнате.
struct Ring {
vector<char> lamp; int pos = 0, n;
Ring(vector<char> l) : lamp(l), n(l.size()) {}
void right() { pos = (pos + 1) % n; }
void left() { pos = (pos + n - 1) % n; }
bool get() const { return lamp[pos]; }
void set(bool x) { lamp[pos] = x; }
};
long long ringLength(Ring& r) {
for (long long L = 1;; L *= 2) {
for (long long i = 0; i < L; i++) { r.set(false); r.right(); } // идём вправо на L шагов и гасим свет
r.set(true); // в конце зажигаем свет
for (long long c = 1; c <= L; c++) { // обратно — не больше L шагов
r.left();
if (r.get()) return c; // встретили свет: круг замкнулся за c шагов
}
// света не встретили: n > L; стоим в стартовой комнате, повторяем с удвоенным L
}
}196:35 Задача с формулами. Вы бьёте врага заклинанием: оно мгновенно наносит $a$ урона, после чего $c$ секунд подряд враг лечится на $b$ в секунду; заклинание можно применять не чаще раза в $d$ секунд (кулдаун). Условие в разборе зачитывали не целиком; судя по выкладкам, нужно найти максимальное здоровье врага, которого можно убить (или понять, что убить можно любого).
198:13 Во-первых, если $a>b\cdot c$, то каждое заклинание «в плюс» (оно наносит больше, чем враг вылечит за $c$ секунд), и убить можно кого угодно. 199:07 Иначе интересны только моменты применения заклинаний: в эти моменты у врага меньше всего здоровья; применять нужно, как только можно (каждые $d$ секунд), иначе он вылечится сильнее. 204:03 Пусть в момент $t=kd$ применено заклинание с номером $k+1$ (счёт с нуля). Тогда суммарный урон равен $a(k+1)$ минус лечение: первое заклинание лечило $kd$ секунд, второе $(k-1)d$ и так далее, всего $b\cdot d\,(1+2+\dots+k)=b\,d\,\dfrac{k(k+1)}{2}$. Получаем
$$D(k)=a(k+1)-b\,d\,\frac{k(k+1)}{2}.$$210:01 Это парабола по $k$ с ветвями вниз — нужно найти её максимум. Можно найти максимум бинпоиском/тернарным поиском, но 211:38 можно и формулой: прирост $D(k)-D(k-1)=a-b\,d\,k$ положителен, пока $k<\dfrac{a}{bd}$, поэтому максимум достигается при $k=\left\lfloor\dfrac{a}{b\,d}\right\rfloor$. В этом режиме ни одно заклинание не лечит дольше $c$ секунд (так как $kd\le a/b\le c$), поэтому формула без ограничения $c$ верна.
// заклинание: мгновенно a урона, затем c секунд подряд враг лечится на b в секунду; применять можно раз в d секунд.
// Максимальное здоровье врага, которого можно убить; -1, если убить можно любого
long long maxKillable(long long a, long long b, long long c, long long d) {
if (a > b * c) return -1; // каждое заклинание «в плюс» — копим урон сколько угодно
long long k = a / (b * d); // после какого заклинания урон перестаёт расти
return a * (k + 1) - b * d * k * (k + 1) / 2;
}Пример (собственный): $a=5$, $b=1$, $c=10$, $d=2$: $k=\lfloor5/2\rfloor=2$, $D(2)=5\cdot3-1\cdot2\cdot3=9$. Если $a=10$, $b=1$, $c=5$ ($a>bc$) — ответ «убить можно любого».
212:53 Даны параболы: одни «смотрят вверх» ($A>0$, «внутри» — точки не ниже параболы), другие «вниз» ($A<0$, «внутри» — не выше). Нужно найти точку, принадлежащую (лежащую внутри) всем параболам. 214:03 Будем смотреть на «верхние» и «нижние» параболы отдельно. Ответ должен лежать выше всех «смотрящих вверх» (огибающая этого семейства — функция $\max_{\text{вверх}} p(x)$) и ниже всех «смотрящих вниз» (функция $\min_{\text{вниз}} q(x)$). Точка с абсциссой $x$ существует тогда и только тогда, когда
$$\max_{\text{вверх}} p(x)\ \le\ \min_{\text{вниз}} q(x).$$217:07 Как говорилось на лекции, максимум выпуклых функций выпуклый, а минимум вогнутых вогнут. Поэтому разность $g(x)=\max p(x)-\min q(x)$ выпукла (как сумма выпуклых: максимум выпуклых и «минус минимум вогнутых»), и её минимум ищем тернарным поиском. Если минимум $g\le0$, то общая точка есть. Это та же задача, что и «возрастающий и убывающий массив», только функции сложнее.
// Параболы y = A x^2 + B x + C. При A > 0 «внутри» — точки не ниже параболы, при A < 0 — не выше.
// Есть ли точка, лежащая внутри всех? max(возрастающие) <= min(убывающие) в некотором x — тернарный поиск
struct Par { double A, B, C; double at(double x) const { return (A * x + B) * x + C; } };
bool commonPoint(const vector<Par>& ps) {
auto g = [&](double x) { // g(x) = max по «верхним» − min по «нижним»; выпукла по x
double up = -1e18, down = 1e18;
for (auto& p : ps) {
if (p.A > 0) up = max(up, p.at(x));
else down = min(down, p.at(x));
}
return up - down; // точка есть, если хотя бы в одном x это <= 0
};
double l = -1e4, r = 1e4;
for (int it = 0; it < 200; it++) {
double m1 = l + (r - l) / 3, m2 = r - (r - l) / 3;
if (g(m1) < g(m2)) r = m2; else l = m1;
}
return g(l) <= 1e-9;
}219:19 В конце — быстрый обзор задач следующего контеста («про линейные алгоритмы»); подробный разбор обещали через неделю.
lower_bound и суффиксные суммы, для функций с одним минимумом — тернарный поиск.