Перебор

1. Полный перебор – самый плохой класс алгоритмов, следует применять, если нет ничего лучше
2. Начинайте с самого простого алгоритма, понижайте сложность усложняясь постепенно
3. Определитесь с видом перебора, один из вариантов может быть гораздо эффективнее другого:
   • Фильтрация – отсечением неподходящих вариантов
   • Генерация – созданием подходящих вариантов
4. Сокращайте пространство поиска как можно раньше
5. Используйте симметрию для уменьшения перебора
6. Используйте предварительные вычисления или кэширование
7. Попробуйте решить задачу "с конца"
8. Оптимизируйте всё, что можно
9. Используйте лучшие структуры данных

---

Перебор с возвратом / Метод ветвей и границ / Backtrack

1. Сокращайте пространство поиска как можно раньше
2. Постарайтесь не использовать рекурсию

---

Разделяй и властвуй

Алгоритм решения

1. Разбейте задачу на подзадачи
2. Решите подзадачу
3. Объедините и получите решение

• ВАЖНО: Подзадачи независимы друг от друга

Особенности

1. Там, где можно применить этот метод, есть "скрытые деревья"
2. Основная сложность состоит в том, что нужно увидеть зависимость целого от части
3. Чаще всего разбиение происходит на 2 части
4. Разделение должно происходить на примерно равные подзадачи

---

Жадные алгоритмы

Итеративно решаете и надеетесь, что всё получится

Особенности

1. Легко придумать
2. Легко оценить сложность
3. Трудно оценить правильность

Свойства решения

1. Оптимальное решение зависит от подоптимального
2. Если оптимальный выбор делается на ${i-ом}$ шаге, то он точно приведёт к оптимальному решению

Советы

1. Если входные данные малого размера, то к задаче вряд ли применяется данный подход
2. Если при сдаче получен статус WA (Wrong Answer), то задача решается другим методом
3. Жадные алгоритмы часто видны при сортировке данных
4. Большинство задач, решаемые данным способом, классические ${=>}$ знание этих задач упрощает решение

---

Динамическое программирование (ДП)

Основные свойства

1. Оптимальное решение зависит от подоптимального
2. Существуют перекрывающиеся задачи

Советы

1. Данный подход часто помогает перейти от перестановок к подмножествам

Типы построения решения

• Восходящее

• Нисходящее

---

AdHoc / Сложные / Специфические

Обычно необходимо просто знать решение задачи этого класса. Или придумать решение задачи на ходу. Очень часть один из гробов.

---

Математика / Вычислительная геометрия

Для закрытия данного класса задач необходимо решать задачи на ProjectEuler и читать соответствующие книги.

---

Рекомендации по книгам

По спортивному программированию

1. Халим С. "Спортивное программирование"
2. Лааксонен А. "Олимпиадное программирование"
3. Скина С. "Олимпиадные задачи по программированию"
4. Долинский М. "Решение сложных и олимпиадных задач по программированию"

По алгоритмам

1. Бхаргава А. "Грокаем алгоритмы"
2. Окулов С. "Динамическое программирование"
3. Окулов С. "Программирование в алгоритмах"
4. Кормен Т. "Алгоритмы. Вводный курс"
5. Кормен Т. "Алгоритмы. Построение и анализ"
6. Скиена С. "Алгоритмы. Руководство по разработке"
7. Седжвик Р. "Алгоритмы на Java"
8. Кнут Д. "Искусство программирования" (7 томов)

---