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

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

Разбиение на тяжелые и легкие строки

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

Утверждение:
Существует не более $2 \cdot \sqrt{\sum ''Доказательство:'' Пусть существует более $2 \cdot \sqrt{\sum

{2} = \sum |S|$, чего не может быть. }} ===='"`UNIQ--h-1--QINU`"'Количество разных длин==== <div style="margin-left: 5px; border-left: solid 1px black; padding-left: 7px"> ''Утверждение: '' Количество различных длин строк не более, чем $O(\sqrt{\sum

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