Задачник Базовый курс EN

Где встречается

геоданные

Статьи

DS Структура данных Декартово дерево Ключ и случайный приоритет: глубина O(log n) в среднем, split и merge, массив с разворотом куска за O(log n). O(log n) в среднем на поиск, вставку, удаление, split и merge 1 задача GRA Алгоритм Минимальное остовное дерево Самая дешёвая сеть, связывающая все вершины: Борувка, Краскал и Прим — три способа применить одну лемму. O(E log V) 2 задачи GRA Алгоритм Тяжёлые пути Запросы на путях дерева: тяжёлые пути режут любой путь на O(log n) отрезков массива под деревом отрезков. O(log² n) на запрос 1 задача GRA Алгоритм Задача коммивояжёра Кратчайший объезд всех точек: ближайший сосед, 2-opt со списками соседей, Or-opt, оценка Хелда — Карпа. NP-трудна; точно O(2ⁿ · n²) 2 задачи DP Приём Оптимизации Кнута и «разделяй и властвуй» 45 тысяч городов на карте по классам населения: 3,5 млн вычислений вместо пяти миллиардов — потому что лучший разрез монотонен. O(k · n log n) 2 задачи DP Алгоритм Алгоритм Витерби Самая правдоподобная цепочка скрытых состояний по шумным наблюдениям: улицы по GPS, участки генома, сообщение по битам. O(T · S²) 2 задачи PAR Приём Жадные алгоритмы Лучший шаг сейчас без оглядки назад: когда это оптимально, когда почти, и как это доказать. обычно O(n log n): сортировка или куча 2 задачи PAR Алгоритм Ближайшая пара точек Две ближайшие точки из n за n log n: разрез, полоса шириной 2d и семь соседей; сеткой — за n в среднем. O(n log n) 2 задачи GEO Приём Векторы и ориентация Знак векторного произведения — поворот налево или направо; на нём стоит почти вся вычислительная геометрия. O(1) на один поворот 2 задачи GEO Алгоритм Пересечение отрезков Где встречаются два отрезка — точно, в дробях; и как найти все встречи среди тысяч отрезков без перебора пар. O(1) на пару; O(n²) перебором для n отрезков 2 задачи GEO Алгоритм Выпуклая оболочка Наименьший выпуклый многоугольник, содержащий все точки, за O(n log n). O(n log n) 2 задачи GEO Алгоритм Точка в многоугольнике Луч из точки пересекает границу нечётное число раз — точка внутри; число оборотов — то же со знаками. O(n) на точку 2 задачи GEO Алгоритм Площадь многоугольника Площадь по координатам вершин: сумма xᵢyᵢ₊₁ − xᵢ₊₁yᵢ, а её знак — направление обхода. O(n) 2 задачи GEO Приём Заметающая прямая Упростите берега мира до 0,2° — и в 72 местах они пересекутся. Прямая с запада на восток найдёт их все, сравнив только соседей. O((n + k) log n) 3 задачи GEO Алгоритм Триангуляция Делоне и диаграмма Вороного Зоны ближайшей точки и треугольники с пустыми окружностями: две стороны одной структуры. O(n log n) в среднем 2 задачи GEO Структура данных k-d дерево Двоичное дерево, которое делит пространство по осям по очереди: ближайшая точка — за десятки шагов вместо перебора. O(n log n) построение; O(log n) на запрос в среднем 1 задача GEO Структура данных R-дерево Окно карты 10° × 5°: из 58 987 отрезков берега R-дерево проверяет 847 прямоугольников. И находит город, дальше всех от моря. окно — число открытых узлов × M; ближайший — обычно O(log n) узлов 1 задача GEO Алгоритм Упрощение линий Рамера — Дугласа — Пекера Упростить ломаную без потери формы: точка, дальше всех от хорды, остаётся, если она дальше допуска. O(n log n) в типичном случае, O(n²) в худшем 2 задачи GEO Приём Кривые Гильберта и geohash Пронумеровать плоскость так, чтобы соседи на карте стояли рядом в одномерном индексе: Z-порядок, geohash, Гильберт. O(k) на номер 1 задача NUM~ Алгоритм Градиентный спуск Ищет минимум функции шагами против градиента — в сторону самого крутого спуска. O(κ · log(1/ε)) шагов 2 задачи ML Алгоритм DBSCAN Собирает в кластеры плотные области точек любой формы, а одинокие точки помечает как шум. O(n·Q + Σ|N(p)|) 2 задачи ML Алгоритм k ближайших соседей Отвечает так, как ответило большинство из k самых похожих известных примеров. O(n · d) на вопрос 2 задачи TEC Приём Сжатие координат Значения до миллиарда заменить их номерами по порядку — и строить массивы и деревья по номерам. O(n log n) на сжатие 2 задачи

Задачи

Сколько выпало дождя Вдоль какой линии Кластеры на карте эпицентров Маршрут по кривой Гильберта Пары ближе r Перекрёсток: внутри, снаружи или на границе Площадь забора Площадь района из нескольких кусков Районы электросети Сейсмическая тревога Склад на сетке улиц Сколько треугольников Сушь Толчки рядом во времени Упростить тропу Честный интервал для озера Ближайшие города Где поставить новую часть Два ближайших города Каналы без помех Карта на всех масштабах Коды городов Ленивый турист Мосты и тоннели Навигатор без тригонометрии План облёта Порог плотности Разрез по меридиану Самый длинный пролёт Сколько людей в прямоугольнике Туда на восток, обратно на запад Что попало в окно Паводок Подписи сёл на карте

Часто рядом

классика 16 точки на плоскости 13 карты и навигация 11 собеседования 9 олимпиады 8 ближайший сосед 6 многоугольник 6 дерево 4 запросы на отрезке 4 наука и физика 4 оптимизация 4 приближение 4