АННОТАЦИЯ 5
Введение 6
1. Способы и методы решения задач олимпиадного программирования 7
1.1. Основные понятия и определения 7
1.2. Олимпиадное программирование 8
1.3. Подходы к решению олимпиадных задач 10
1.4. Существующая классификация задач спортивного программирования 10
1.4.1. Задачи на структуры данных 11
1.5. Двоичные деревья поиска и различные методы их балансировки 12
1.5.1. Аналоги двоичных деревьев поиска, применяемые в задачах 14
1.5.2. Разновидности декартовых деревьев 14
1.6. Выводы по первой главе 16
2. Декартовые деревья как особая разновидность двоичных деревьев поиска 18
2.1. Особенности задач на декартовые деревья 18
2.1.1. Решение задач с использованием декартовых деревьев 19
2.2. Задачи, в которых применение декартовых деревьев необходимо 19
2.2.1. Задача «Поединок с И-Так-Понятно-Кем» 19
2.2.2. Задача «Окончательная структура» 21
2.2.3. Задача «Последовательность» 24
2.3. Сравнение декартовых деревьев с аналогами в случае их применимости 26
2.3.1. Задача «Биржа» 26
2.3.2. Задача «Burek» 28
2.3.3. Задача «Snow White» 30
2.3.4. Задача «Отрезки на прямой возвращаются» 31
2.4. Выводы по второй главе 33
3. Разработка и анализ алгоритмов 34
3.1. Задача «Поединок с И-Так-Понятно-Кем» 34
3.2. Задача «Окончательная структура» 37
3.3. Задача «Последовательность» 42
3.4. Задача «Биржа» 42
3.5. Задача «Burek» 47
3.6. Задача «Snow White» 50
3.7. Задача «Отрезки на прямой возвращаются» 52
3.8. Выводы по третьей главе 54
Заключение 55
Литература 56
ПРИЛОЖЕНИЕ 1. Программная реализация разработанных алгоритмов 55
Олимпиады по программированию проводятся различными компаниями с конца XX века и успели зарекомендовать себя как способ выявить программистов, обладающих умением решать разнообразные задачи. При этом сами навыки спортивного программирования передаются от одних участников к другим, однако непосредственно умению решать задачи почти не учат, вместо этого призывая к накоплению собственного опыта, изучению теоретических основ и ознакомлению с разборами, проводимыми жюри соревнований или другими участниками.
В данной работе предполагается, что подобный подход недостаточно эффективен для быстрого и успешного решения задач, откуда следует предложение взглянуть на проблему иначе. Для исследования выбрана тема, с одной стороны достаточно редкая, чтобы участники не обладали достаточным опытом для её безошибочного распознавания, с другой — встречающаяся с достаточной частотой, чтобы у программистов имелась реальная возможность с ней столкнуться.
Такой темой оказалась структура данных, известная как декартовое (иногда также употребляется вариант «декартово») дерево, оно же трип или дерамида. Была поставлена цель определить чем задачи, в которых требуется использование этой структуры данных, отличаются от прочих. В результате выяснилось, что действительно существует такой критерий, его получение и использование описаны далее.
В результате теоретического анализа свойств декартовых деревьев, а также других структур данных и приёмов, позволяющих решать некоторые из доступных дерамидам задач, был выдвинут критерий: трип целесообразно использовать для решения задачи тогда и только тогда, когда среди запросов одновременно имеются множественные запросы и запросы, характерные для двоичных деревьев поиска, либо присутствуют уникальные запросы декартовых деревьев, при этом саму задачу необходимо решать в режиме онлайн.
Попытки использовать критерий на практике показали, что он действительно применим и корректно отражает существующие закономерности, связывающие метод решения, время работы, объём используемой памяти и размер самой программы. В процессе были подтверждены известные результаты о соотношении эффективности рассмотренных методов, что является независимым показателем корректности проделанных выкладок.
Таким образом, принятие выдвинутого критерия гораздо более вероятно, чем его отклонение.
