Во сколько раз длиннее по улицам
Служба доставки прикидывает длину поездки, ещё не построив маршрут: расстояние по прямой умножает на коэффициент k — по улицам ведь всегда дальше, чем по прямой. Каким взять k? Есть журнал из n поездок: для каждой известно расстояние по прямой ai и длина настоящего маршрута по улицам bi. Выберите k, при котором сумма квадратов промахов
$$\sum_{i=1}^{n} \bigl(b_i - k\,a_i\bigr)^2$$наименьшая, и посчитайте типичный промах такой прикидки — корень из среднего квадрата: √(Σ(bi − kai)² / n).
Свободного члена в модели нет: поездка нулевой длины по прямой и по улицам — ноль. Такие поездки в журнале тоже бывают — заказ забрали и отдали на одном перекрёстке.
Два теста — настоящий Алматы из OpenStreetMap: пары перекрёстков центра города, расстояние между ними по прямой и кратчайший путь по улицам.
Вход
В первой строке число n (1 ≤ n ≤ 200 000). В каждой из следующих n строк два целых числа ai и bi — расстояние по прямой и по улицам в метрах (0 ≤ ai, bi ≤ 10⁶). Хотя бы одно ai больше нуля.
Выход
Два числа через пробел: коэффициент k и типичный промах в метрах. Ответ засчитывается, если каждое число отличается от верного не больше чем на 10⁻⁶ (для чисел больше единицы — не больше чем на 10⁻⁶ от их величины).
Примеры
Пример 1
3 100 130 200 250 400 560
1.366666667 15.986105
Пример 2
3 0 0 1000 1500 10 50
1.500349965 20.206249
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 10 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Формула наклона из статьи выведена для прямой со свободным членом: такая прямая проходит через центр масс точек. Здесь прямая обязана пройти через начало координат. Повторите вывод для модели b ≈ ka: от чего здесь берут производную и что приравнивают нулю?
2Подсказка 2
Производная суммы Σ(bi − kai)² по k равна −2Σai(bi − kai). При каком k она обращается в ноль?
3Идея
Это нормальное уравнение для таблицы из одного столбца a, без столбца единиц: (Σai²)·k = Σaibi, откуда k = Σaibi / Σai². Геометрически это проекция вектора длин по улицам на вектор длин по прямой. Вторая производная 2Σai² положительна (хотя бы одно ai не ноль), так что это минимум.
Заметьте, что каждая поездка входит в ответ с весом ai²: длинная поездка весит намного больше короткой. Это свойство квадратов, а не случайность: промах длинной поездки в метрах больше, и метод старается в первую очередь его.
4Разбор
Один проход — две суммы, Σab и Σa². Обе целые: в Python они точные, в Go помещаются в int64 (не больше 2·10⁵ · 10¹² = 2·10¹⁷). Делим и получаем k. Поездки нулевой длины ничего не добавляют ни в одну сумму и обрабатываются сами собой.
Второй проход считает сумму квадратов остатков bi − kai, и типичный промах — корень из её среднего.
На двух тестах из Алматы k выходит около 1,27–1,28: путь по улицам центра города в среднем на четверть с небольшим длиннее, чем по прямой, а типичный промах такой прикидки — семьсот-восемьсот метров.
4+Решение
5Сложность
O(n) времени. Память можно сделать O(1), если читать поток дважды, но хранить 2·10⁵ пар тоже не страшно.
6Типичные ошибки
- Среднее отношений. Посчитать bi/ai для каждой поездки и усреднить — естественная мысль, но это другой ответ: в нём поездка в пятьдесят метров весит столько же, сколько поездка в пять километров, а короткие поездки как раз петляют сильнее всех. В первом примере среднее отношений 1,3167 вместо 1,3667, в десятом тесте разница в разы. К тому же отношение не определено для поездок нулевой длины.
- Формула со свободным членом. Прямая a + bx из статьи ложится на точки лучше, но это не та модель: у неё на нулевом расстоянии получается ненулевая длина маршрута.
- Сумма квадратов остатков через Σb² − kΣab. В точке минимума это верное тождество, и в статье оно экономит второй проход. Но в тесте 9 обе суммы около 10¹⁷, а их разность — около половины: в числах с плавающей точкой от неё не остаётся ни одного верного знака, а то и выходит отрицательное число под корнем. Когда модель почти идеальна, остатки надо складывать напрямую.
- Переполнение. Σab не помещается в 32-битное целое уже на тестах с настоящими поездками по Алматы.