Хлопці та дівчата#11810

Хлопці та дівчата (Розбір)

Автор задачі:	Антон Тригуб
Задачу підготував:	Олександр Гроскопф
Розбір написав:	Павло Цікалишин

10pt

Блок 1

Якщо в множині вже є хоча б один хлопець певного типу $x$ , то всі інші хлопці цього ж типу також мають бути присутні. Отже, ми можемо перебирати всі підмножини типів хлопців, перевіряти, чи вони задовольняють умову задачі, та вибирати найкращий варіант.

Блок 2

Розглянемо задачу як граф, де вершини відповідають дівчатам, а хлопці є ребрами, що з'єднують ці вершини. Нам потрібно, щоб усі ребра в множині мали хоча б одну спільну вершину. Такі структури можуть бути лише двох типів:

Зірка — всі ребра виходять із однієї вершини.
Трикутник — три вершини, кожна з яких з'єднана з двома іншими.

Щоб знайти відповідь для зірки, достатньо визначити її центр $x$ і підрахувати суму всіх ребер, що виходять із цієї вершини.

Для трикутника потрібно перебрати всі ребра $(u, v)$ і знайти вершину, разом із якою вони утворюють трикутник.

Блок 3

Оскільки кожна вершина може мати не більше двох вихідних ребер, ми можемо перебрати всі вершини, що мають рівно два сусіди, і перевірити, чи ці сусіди також з'єднані між собою. Якщо так, то знайдено трикутник.

Блок 4

У цій групі достатньо для кожної вершини $x$ перебрати всі пари її сусідів $(u, v)$ . Потім перевіряємо, чи існує ребро між вершинами $u$ і $v$ . Це працює за складністю $O (n^{2})$ \mathcal{O}(n^2), оскільки кожна вершина може мати до $n$ сусідів.

Блоки 5

Щоб швидко знайти всі трикутники, можна розділити вершини на важкі (з більш ніж $n$ \sqrt{n} сусідами) і легкі (з меншою кількістю сусідів).

Спочатку рахуємо всі трикутники, що містять хоча б одне легке ребро. Це можна зробити так само, як у попередньому підході, і це займе $O (n n)$ \mathcal{O}(n\sqrt{n}) часу. Потім знаходимо трикутники, що складаються тільки з важких вершин. Для цього видаляємо всі легкі вершини та повторюємо підрахунок. Це також виконується за $O (n n)$ \mathcal{O}(n\sqrt{n}).

Загальна складність алгоритму — $O (n n)$ \mathcal{O}(n\sqrt{n}).

Блок 6-7

Щоб знайти найкращий трикутник, потрібно для кожної вершини $x$ розглянути трикутник, утворений двома найбільшими ребрами, що виходять з $x$ (якщо такий існує). Таких трикутників є $O (n)$ , тому отримаємо розв'язок за $O (n lo g n)$ O(n \log n) або $O (n)$ в залежності від способу пошуку третього ребра таких трикутників.

Доведемо, що якщо оптимальна відповідь є трикутником, то ми її розглянемо. Дійсно, нехай оптимальна відповідь є трикутником зі сторонами, що мають ваги $l_{1}, l_{2}, l_{3}$ l_1, l_2, l_3, $l_{1} ⩽ l_{2} ⩽ l_{3}$ l_1 \leqslant l_2 \leqslant l_3. Нехай з вершини, що знаходиться між ребрами $l_{2}$ l_2 та $l_{2}$ l_2 (позначимо її $v$ ) виходить ще якесь ребро $r > b$ r > b. Тоді зірка з центром в $v$ буде кращою відповіддю, ніж наш трикутник:

[ зірка l_2 + l_3 + r > l_2 + l_3 + l_1 = трикутник ].