Сколько соседей спросить о глубине
Сейсмолог хочет по одному лишь положению эпицентра угадать, насколько глубоко произошло землетрясение: мелкие очаги (глубже поверхности меньше чем на 70 км), промежуточные (70–300 км) или глубокие (от 300 км). Способ — k ближайших соседей по каталогу уже случившихся толчков. Осталось выбрать k.
Проверьте каждое k от 1 до K честно, без отдельной проверочной выборки: по очереди уберите из каталога каждый толчок и спросите о нём остальные. Сосед — другой толчок каталога; расстояние — обычное, по прямой в пространстве; соседи упорядочены по расстоянию, а при равном расстоянии — по номеру во входе; при равенстве голосов побеждает класс того из претендентов, кто ближе всех. Для каждого k посчитайте, сколько толчков угадано верно, и назовите лучшее k (из равных — наименьшее).
Три теста — настоящие землетрясения магнитудой от 5 за 2015–2025 годы из каталога USGS: эпицентр задан точкой на шаре радиусом 6371 км, координаты в километрах.
Вход
В первой строке числа n и K (2 ≤ n ≤ 1000, 1 ≤ K ≤ min(50, n − 1)). В каждой из следующих n строк — целые координаты x, y, z (по модулю не больше 10⁴) и класс глубины c: 0 — мелкий, 1 — промежуточный, 2 — глубокий.
Выход
В первой строке — лучшее k и число верно угаданных при нём толчков. Во второй — K чисел: сколько толчков угадано при k = 1, 2, …, K.
Примеры
Пример 1
7 4 0 0 0 0 10 0 0 0 0 10 0 0 100 100 0 2 110 100 0 2 105 104 0 0 50 50 0 1
1 3 3 3 3 3
Ограничения
- Время · Python
- 8000 мс
- Время · Go
- 2000 мс
- Память
- 256 МБ
- Проверка
- 7 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Решение в лоб — для каждого k заново для каждого толчка найти k соседей и проголосовать — стоит O(K·n²), до 50 миллионов расстояний. А что общего у ответов для k = 5 и k = 6 для одного и того же толчка?
2Подсказка 2
Шесть ближайших соседей — это пять ближайших и ещё один. Отсортируйте соседей каждого толчка один раз и добавляйте голоса по одному. Как при этом быстро узнавать победителя с правилом ничьей?
3Идея
Для каждого толчка один раз находим K ближайших других толчков в правильном порядке. Дальше k растёт от 1 до K, и на каждом шаге добавляется ровно один голос. Классов всего три, поэтому победителя можно выбирать заново на каждом шаге за O(1): у кого больше голосов, а при равенстве — чей первый голос пришёл раньше. «Первый голос раньше» — то же самое, что «ближайший из претендентов» в правиле ничьей.
Это скользящий контроль с исключением по одному (leave-one-out): каждый пример по очереди становится экзаменом для остальных. Отложенная выборка дешевле, но тратит часть данных только на проверку; здесь проверяется всё, и при этом ни один толчок не голосует сам за себя.
4Разбор
Для толчка i перебираем все j ≠ i, считаем квадрат расстояния в целых числах (не больше 1,2·10⁹, так что хватает и 32-битного целого) и держим K лучших пар (расстояние, номер). Потом идём по ним, обновляя счётчики голосов и позицию первого голоса каждого класса, и после каждого шага прибавляем единицу к счёту этого k, если победитель совпал с настоящим классом. В конце выбираем k с наибольшим счётом.
На настоящем каталоге лучшими оказываются маленькие k — один-три соседа, — и угадывается больше восьмисот толчков из тысячи. Глубокие толчки не рассеяны по планете: они идут полосами вдоль плит, которые погружаются в мантию, и ближайший толчок обычно той же глубины.
4+Решение
5Сложность
O(n² log K) на поиск соседей и O(n·K) на подсчёт: миллион расстояний при n = 1000.
6Типичные ошибки
- Толчок среди собственных соседей. Самая частая ошибка проверки моделей: он ближе всех к себе и всегда угадывает свой класс, и k = 1 выглядит идеальным. Пример это ловит.
- Каждое k с нуля. Верно, но в 50 раз дольше.
- Ничья по меньшему номеру класса. При чётных k ничьи часты, и ответ расходится с правилом.