Выборка по энергии
Сейсмологи хотят разобрать вручную k землетрясений из каталога, выбранных случайно, но так, чтобы сильные попадали чаще слабых — пропорционально выделенной энергии. Энергия землетрясения магнитуды M пропорциональна 101,5·M: на единицу магнитуды — примерно в 31,6 раза больше. Каталог приходит потоком, и хранить его целиком не хочется.
Решили использовать взвешенную резервуарную выборку Эфраимидиса — Спиракиса. Событию с весом w = 101,5·M и случайным числом u из интервала (0, 1) присваивается ключ u1/w, и в выборку попадают k событий с наибольшими ключами. Чтобы результат можно было проверить, случайные числа уже записаны в каталог рядом с магнитудами.
Выведите номера выбранных событий.
Вход
В первой строке n и k (1 ≤ k ≤ n ≤ 6·104). Дальше n строк: магнитуда M (от 5,00 до 9,50, две цифры после точки) и число u (0 < u < 1, девять цифр после точки). События нумеруются с единицы в порядке входа. Гарантируется, что k-й и (k + 1)-й ключи по убыванию различаются заметно, и ответ не зависит от ошибок округления, если считать аккуратно.
Выход
Номера k выбранных событий по возрастанию через пробел.
Примеры
Пример 1
4 2 5.00 0.500000000 6.00 0.500000000 5.50 0.900000000 5.00 0.990000000
3 4
Пример 2
3 1 5.00 0.999999999 7.00 0.000000001 6.00 0.500000000
1
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 10 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Посчитайте u1/w для землетрясения магнитуды 9,5 и u = 0,5. Сколько знаков после запятой нужно, чтобы отличить его от единицы — и от ключа такого же события с u = 0,500001?
2Подсказка 2
Сравнивать можно не сами ключи, а любую возрастающую или убывающую функцию от них. Какая функция превратит u1/w в сумму двух обычных чисел?
3Идея
Ключ u1/w при M = 8 и u = 0,5 равен 1 − 6,9·10−13, а при M = 9,5 — 1 − 3,9·10−15: у самых сильных событий ключи отличаются от единицы и друг от друга в последних битах числа с плавающей точкой, и порядок между ними решало бы округление. Сравнивать можно не сами ключи, а их логарифмы: ln u1/w = ln u / w. Это маленькие отрицательные числа, но относительная точность у них та же, что у любых других. Удобнее ещё раз взять логарифм от минуса: ln(−ln u) − ln w = ln(−ln u) − 1,5·M·ln 10 — тогда и вес 101,5·M считать не нужно. Эта величина убывает с ростом ключа, значит, нужны k событий с наименьшими её значениями. Держим их в куче размера k, как в любой задаче «k лучших из потока».
4Разбор
Куча хранит k лучших событий, сверху — худшее из них. Новое событие вытесняет его, если лучше. После прохода сортируем номера.
Первый пример показывает, что случайность здесь настоящая. Событие M6,0 с u = 0,5 сильнее события M5,0 в 31,6 раза, но проигрывает ему, когда у того u = 0,99. Ключи сравниваются через ln u/w: −0,693/31,6 = −0,0219 против −0,0101 (обе величины — в единицах 1/w слабого события). Во втором примере событие M5,0 с u, почти равным единице, обходит M7,0, которому выпало u = 10−9. На настоящем каталоге выборка почти целиком состоит из сильных событий, потому что энергии различаются в тысячи раз, но не только из самых сильных.
Почему ключ u1/w делает то, что нужно. Для первого места — события с наибольшим ключом — можно проверить прямо: вероятность, что им станет событие i, равна wi/(w1 + … + wn), ровно пропорционально весу. Дальше то же самое повторяется среди оставшихся: так устроена выборка с весами без возвращения, и Эфраимидис и Спиракис доказали это в 2006 году. В отличие от ключа «u, умноженное на w», который кажется естественным, но пропорциональности не даёт.
4+Решение
5Сложность
O(n log k) времени и O(k) памяти: один проход и куча размера k.
6Типичные ошибки
- Ключ u·w. Он тоже предпочитает тяжёлые события, но не пропорционально весу. При весах, которые различаются в тысячи раз, он просто выбирает самые сильные землетрясения: первый пример.
- Считать u^(1/w) напрямую. Ключи сильных событий отличаются друг от друга в последних битах, и выбор между ними станет делом округления.
- Сортировать весь поток. Верно, но O(n log n) и вся выборка в памяти; куча из k элементов обходится одним проходом.