Разбор задачи Ханты-Мансийск - Париж

Август 21, 2022

Главная
Менеджмент
Разбор задачи Ханты-Мансийск - Париж

Содержание

2. Основная идея Если можно передавать сообщение напрямую, то это выгоднее, чем в обход Таким образом, необходимо
3. Решение за O(n^3) Перебрать через кого в Дубае, Москве и Калининграде передается сообщение и посчитать стоимость
4. Построение графа Вершины – люди Ребра – стоимость передачи сообщения напрямую от одного человека к другому
5. Поиск кратчайшего пути Алгоритм Флойда за O(n^3) – 40 баллов Алгоритм Дейкстры за O(n^2) – 60
6. Динамическое программирование (ДП) Для каждого человека считать минимальную стоимость передачи сообщения этому человеку Считать последовательно для
7. ДП за O(n^2) Для каждого человека перебирать кто из предыдущего часового пояса передает ему сообщение Стоимость
8. Улучшение ДП за O(n^2) Когда n - большое Для каждого часового пояса оставлять некоторое количество самых
9. ДП за O(n log n) Все номера в каждой зоне – отсортированы Для каждой длины совпадающего
10. ДП за O(n) Все номера в каждом поясе – отсортированы Идея «двух указателей» и два прохода
11. ДП за O(n) При перемещении указателя в предыдущем поясе эти значения пересчитываются Для человека в текущем
12. Meet-in-the-middle Считать для каждого человека из Москвы минимальную стоимость передачи сообщения ему из Ханты-Мансийска и от
13. «Жадные» решения Каждый раз выбирать ближайший номер в следующем часовом поясе 24 балла
15. Скачать презентацию

Слайд 2

Основная идея
Если можно передавать сообщение напрямую, то это выгоднее, чем в

обход
Таким образом, необходимо передавать в следующий часовой пояс
Всегда происходит ровно четыре передачи
Друзья в часовых поясах Ханты-Мансийска и Парижа не нужны

Слайд 3

Решение за O(n^3)
Перебрать через кого в Дубае, Москве и Калининграде передается

сообщение и посчитать стоимость такой передачи
40 баллов

Слайд 4

Построение графа
Вершины – люди
Ребра – стоимость передачи сообщения напрямую от одного

человека к другому
Всего O(n) вершин и O(n^2) ребер

Слайд 5

Поиск кратчайшего пути
Алгоритм Флойда за O(n^3) – 40 баллов
Алгоритм Дейкстры за

O(n^2) – 60 баллов
Поиск кратчайшего пути в ациклическом графе за O(n^2) – 60 баллов

Слайд 6

Динамическое программирование (ДП)
Для каждого человека считать минимальную стоимость передачи сообщения этому

человеку
Считать последовательно для часовых поясов Дубая, Москвы и Калинирграда

Слайд 7

ДП за O(n^2)
Для каждого человека перебирать кто из предыдущего часового пояса

передает ему сообщение
Стоимость равна сумме минимальной стоимости передать этому человеку из предыдущего пояса и стоимости последнего сообщения
Стоимость передачи этому человеку – минимум из таких стоимостей
60 баллов

Слайд 8

Улучшение ДП за O(n^2)
Когда n - большое
Для каждого часового пояса оставлять

некоторое количество самых лучших значений
Если оставлять около 3000 – 70 баллов

Слайд 9

ДП за O(n log n)
Все номера в каждой зоне – отсортированы
Для

каждой длины совпадающего префикса, используя двоичный поиск, находится отрезок людей в предыдущей зоне с таким префиксом
Находится минимум на этом отрезке, например с использованием дерева отрезков.
Каждый подсчет значения – за O(log n)
100 баллов

Слайд 10

ДП за O(n)
Все номера в каждом поясе – отсортированы
Идея «двух указателей»

и два прохода в разных направлениях
В предыдущем часовом поясе указатель указывает на строку, меньшую строки в текущем
Для каждой длины префикса хранится минимальная стоимость передать сообщение людям в предыдущем поясе с совпадающим префиксом

Слайд 11

ДП за O(n)
При перемещении указателя в предыдущем поясе эти значения пересчитываются
Для

человека в текущем поясе стоимость считается, перебирая длину совпадающего с человеком из предыдущего пояса префикса
Сортировать можно за O(n) цифровой сортировкой, но можно и за O(n log n)
100 баллов

Слайд 12

Meet-in-the-middle
Считать для каждого человека из Москвы минимальную стоимость передачи сообщения ему

из Ханты-Мансийска и от него в Париж
Передавать сообщение человеку А, живущему в Москве, из Ханты-Мансийска нужно через человека с ближайшим номером или к Поликарпу, или к А
Считать можно за O(n) «двумя указателями»
100 баллов

Слайд 13

Разбор задачи Ханты-Мансийск - Париж

Содержание

Основная идеяЕсли можно передавать сообщение напрямую, то это выгоднее, чем в

Решение за O(n^3)Перебрать через кого в Дубае, Москве и Калининграде передается

Построение графаВершины – людиРебра – стоимость передачи сообщения напрямую от одного

Поиск кратчайшего путиАлгоритм Флойда за O(n^3) – 40 балловАлгоритм Дейкстры за

Динамическое программирование (ДП)Для каждого человека считать минимальную стоимость передачи сообщения этому

ДП за O(n^2)Для каждого человека перебирать кто из предыдущего часового пояса

Улучшение ДП за O(n^2)Когда n - большоеДля каждого часового пояса оставлять

ДП за O(n log n)Все номера в каждой зоне – отсортированыДля

ДП за O(n)Все номера в каждом поясе – отсортированыИдея «двух указателей»

ДП за O(n)При перемещении указателя в предыдущем поясе эти значения пересчитываютсяДля

Meet-in-the-middleСчитать для каждого человека из Москвы минимальную стоимость передачи сообщения ему

«Жадные» решенияКаждый раз выбирать ближайший номер в следующем часовом поясе24 балла

Похожие презентации