# конспект · шаг 7 из 7
Конспект: пять задач из практики
Понятия
Проверка ступенями - дешёвый признак отсеивает большинство кандидатов, дорогая точная проверка работает только внутри групп с равным признаком.
Каноническая форма - преобразование, после которого равные по смыслу объекты равны побайтно.
Взвешенная медиана - точка, левее которой набирается половина суммарного веса; минимизирует сумму взвешенных расстояний на прямой.
Соединение - отрезок рейса: откуда, куда, когда отправился, когда прибыл. Просмотр соединений - один проход по ним в порядке отправления даёт самое раннее прибытие.
Множество Парето - варианты, которые никто не обгоняет: нет другого, не худшего по всем критериям и строго лучшего хотя бы по одному.
Расстояние Левенштейна - вставки, удаления, замены. Дамерау-Левенштейна - плюс перестановка соседних символов.
Что унести
КОПИИ ФАЙЛОВ
размер (бесплатно) -> хеш (одно чтение) -> побайтно (при равных хешах)
80 файлов: 3160 сравнений пар -> 17; 21 086 байт -> 6664
хеш совпал = кандидат; удалять только после побайтной проверки
«одинаковые по смыслу» -> каноническая форма -> точные копии
сумма кодов символов склеила port=8/log=on0 с port=80/log=on
СКЛАД НА ТРАССЕ
сумма пробега с весами -> взвешенная медиана (55-й км, 916 км/день)
сумма без весов -> медиана (10-й км, 1580)
самый дальний -> середина крайних (29-й км, 1234)
сдвиг на 1 км меняет сумму на (вес слева - вес справа)
два склада на прямой: разрез сортированного списка, 5 вместо 1378
k складов на плоскости (k-медиана) - NP-трудна
РАСПИСАНИЕ
граф длительностей не знает времени: обещал 8:32, реально 8:42
соединения по отправлению, rano[станция]; если успеваем - улучшаем
выезд 8:04 -> 8:42; 8:06 -> маршрута нет
время + пересадки: (8:42, 2), (8:50, 1), (9:30, 0) - Парето
RAPTOR: раунд k - лучшие прибытия с не более чем k поездками
ПОДСКАЗКИ И ОПЕЧАТКИ
словарь готовят один раз; запрос стоит по своей длине
префикс p: [первый >= p, первый >= p + "~") - 2 log₂ n сравнений
одна правка: до 53n + 25 строк, проверка в множестве
kavre -> kaver: Дамерау 1, Левенштейн 2 - решает спецификация
ОБЩЕЕ ОКНО
все участники -> одна лента, сортировка по началу
svoboden_s = max(svoboden_s, конец); окно, если начало - svoboden_s >= d
не забыть хвост до R и занятость за пределами [L, R)
шаг в минуту пропускает окно с 10:15:20
Ловушки джокера
Удалили по хешу. Слабый хеш склеивает разные файлы - данные пропадают.
Критерий «лучше» выбран молча. Медиана, середина и медиана без весов дают три разных склада и разницу в пробеге до 72%.
Граф без времени для расписания. Ответ правдоподобный и недостижимый.
Один «лучший» маршрут при двух критериях. Человеку с чемоданом нужна поездка без пересадок.
Запрос стоит по размеру словаря. Миллион проверок на каждое нажатие клавиши.
Граница свободы без max. Короткая встреча внутри длинной «освобождает» человека раньше времени.
Комментарии
Пока нет комментариев. Будь первым!
Оставить комментарий