Ленивый турист
Ленивый турист гуляет по перекрёсткам города. Раз в минуту он выбирает наугад одну из улиц, которые выходят из его перекрёстка, — все равновероятно. Если улица ведёт к перекрёстку не выше нынешнего, турист идёт по ней. Если выше на Δ метров, он идёт по ней с вероятностью e−Δ/T, а иначе остаётся на месте и через минуту выбирает снова. Это отжиг при постоянной температуре T, где энергия — высота над морем, а ход — переход по улице.
Турист гуляет бесконечно долго. Какую долю минут он проведёт на каждом перекрёстке?
Вход
В первой строке числа n, m и T — перекрёстки, улицы и температура в метрах (2 ≤ n ≤ 50 000, 1 ≤ m ≤ 100 000, 1 ≤ T ≤ 106). Во второй — высоты перекрёстков h1, …, hn, целые, от 0 до 106 метров. Дальше m строк по два числа a b — улица между перекрёстками a и b, по ней можно идти в обе стороны. Улица не соединяет перекрёсток сам с собой, двух улиц между одной парой перекрёстков нет, и из любого перекрёстка можно дойти до любого.
Выход
n чисел через пробел или с новой строки: долю времени, которую турист проводит на перекрёстках 1, …, n. Ответ засчитывается, если каждое число отличается от точного не больше чем на 10−6.
Примеры
Пример 1
3 2 1 700 700 700 1 2 2 3
0.2500000000 0.5000000000 0.2500000000
Пример 2
4 4 2 0 2 2 4 1 2 1 3 1 4 2 4
0.6858226237 0.1682000290 0.0841000145 0.0618773327
Ограничения
- Время · Python
- 6000 мс
- Время · Go
- 2000 мс
- Память
- 256 МБ
- Проверка
- 10 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Начните с первого примера. Все три перекрёстка на одной высоте, так что турист идёт по любой улице, которую выбрал. Почему средний перекрёсток получает половину времени, а не треть? Посчитайте, сколько раз за долгую прогулку турист приходит на средний перекрёсток и сколько — на крайние.
2Подсказка 2
Предположите, что доля перекрёстка v пропорциональна deg(v)·e−h(v)/T, где deg(v) — число его улиц, и проверьте: течёт ли по каждой улице за минуту столько же вероятности туда, сколько обратно?
3Идея
Пусть π(v) = deg(v)·e−h(v)/T / Z. Возьмём улицу между u и v. Из u турист выбирает её с вероятностью 1/deg(u) и идёт по ней с вероятностью min(1, e−(h(v) − h(u))/T). Поток вероятности по улице из u в v:
π(u) · (1/deg(u)) · min(1, e−(h(v) − h(u))/T) = min(e−h(u)/T, e−h(v)/T) / Z.
Степень сократилась, и выражение симметрично: обратный поток такой же. Значит, π стационарно — так же, как в доказательстве теоремы о распределении Больцмана в статье, только там у всех состояний было одинаковое число соседей, и множитель deg(v) был общим. Граф связен, поэтому стационарное распределение единственно, а доля времени на каждом перекрёстке за бесконечно долгую прогулку равна ему (это эргодическая теорема для цепей Маркова; она верна и тогда, когда блуждание ходит по кругу, как в первом примере, где турист чередует средний перекрёсток и крайние).
Вывод для отжига: если у состояний разное число соседей, блуждание при постоянной температуре предпочитает состояния, где соседей больше. Чтобы вернуть чистое распределение Больцмана, ход из u в v принимают с вероятностью min(1, deg(u)/deg(v)·e−(h(v) − h(u))/T) — это поправка Хастингса (1970).
4Разбор
Посчитайте степени, вычтите из всех высот наименьшую, возьмите веса deg(v)·e−(h(v) − hmin)/T и разделите на их сумму. Вычитать минимум нужно обязательно: в третьем тесте перепад высот миллион метров при T = 1, и без вычитания все веса превращаются в ноль.
Во втором примере у низкого перекрёстка три улицы и вес 3, у двух на высоте 2 — веса 2e−1 и e−1, у самого высокого — 2e−2; сумма 4,374, и низкий перекрёсток получает 0,686 времени. Без поправки на степени было бы 0,534.
4+Решение
5Сложность
O(n + m): один проход по улицам, чтобы посчитать степени, и один по перекрёсткам.
6Типичные ошибки
- Чистый Больцман e−h/T. Верен, только когда у всех перекрёстков одинаковое число улиц. На первом же примере даёт по трети вместо ¼, ½, ¼.
- Экспонента без вычитания минимума. e−106 в числах с плавающей точкой — ноль, и сумма весов тоже ноль.
- Моделирование прогулки. Доли, посчитанные по случайной прогулке, сходятся как 1/√(число шагов): для точности 10−6 нужны триллионы шагов. А при низкой температуре прогулка ещё и надолго застревает в низинах — это то же самое, что ловушка в статье.
- Степенной метод — умножать распределение на матрицу переходов, пока не перестанет меняться. На холодных тестах он сходится медленно по той же причине; формула точнее и быстрее.