Корневая на строках: различия между версиями
KiKoS (обсуждение | вклад) м (author) |
Глеб (обсуждение | вклад) |
||
Строка 2: | Строка 2: | ||
====Разбиение на длинные и короткие строки==== | ====Разбиение на длинные и короткие строки==== | ||
− | Назовем строку $S \textit{длинной}$, если $|S| \ge \sqrt{\sum |S|}$. Все оставшиеся строки назовем $\textit{короткими}$. | + | Назовем строку $S \ \textit{длинной}$, если $|S| \ge \sqrt{\sum |S|}$. Все оставшиеся строки назовем $\textit{короткими}$. |
{{Утверждение | {{Утверждение | ||
|Утверждение=Существует не более <nowiki>$\sqrt{\sum |S|}$</nowiki> длинных строк. | |Утверждение=Существует не более <nowiki>$\sqrt{\sum |S|}$</nowiki> длинных строк. |
Текущая версия на 13:57, 22 октября 2019
Данные идеи очень полезны в задачах, где есть ограничение на суммарный размер строк. Обозначим это ограничение за $\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