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

Данные идеи очень полезны в задачах, где есть ограничение на суммарный размер строк. Обозначим это ограничение за $\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