Корневая на строках

Данные идеи очень полезны в задачах, где есть ограничение на суммарный размер строк. Обозначим это ограничение за $\sum |S|$.

Разбиение на длинные и короткие строки

Назовем строку $S \ \textit{длинной}$, если $|S| \ge \sqrt{\sum |S|}$. Все оставшиеся строки назовем $\textit{короткими}$.

Утверждение:
Существует не более $\sqrt{\sum |S|}$ длинных строк.

Доказательство:
Пусть существует более $\sqrt{\sum | S | }$ длинных строк. Тогда их суммарная длина больше, чем $\sqrt{\sum | S | } \cdot \sqrt{\sum | S | } = \sum | S | $, чего не может быть.

Количество разных длин

Утверждение:
Количество различных длин строк не более, чем $O(\sqrt{\sum |S|})$.

Доказательство:
Пусть количество различных длин равно $x$. Тогда минимальная возможная сумма длин~--- это сумма чисел от 1 до $x$. $$\sum_{i=1}^x i = \frac{x(x + 1)}{2}$$ Так как это число должно быть меньше, чем $\sum |S|$, то $x = O(\sqrt{\sum |S|})$

---

Автор конспекта: Константин Амеличев

По всем вопросам пишите в telegram @kik0s