16 августа 2019 года в 22:00 (время московское) заканчивается второй этап SnarkNews Summer Series 2019. Как и несколько предыдущих серий, SNSS-2019 проходит на системе Яндекс.Контест. Опубликовано расписание серии.
По просьбам участников отдельно публикую ссылку для регистрации и входа во второй раунд. В комментариях к этому сообщению по окончании раунда в соответствии с расписанием можно будет обсудить задачи первого раунда.
Как решать задачи E и F? По идее в задаче F мы должны сделать число золотых слитков в каждом городе только средним значением или средним значением плюс один и на этом сделать дп :)
Е: считаешь количество пар $$$i<j$$$ таких что $$$a_i<a_j$$$ и таких что $$$a_i>a_j$$$, перемножаешь, затем ищешь количество троек $$$i<j<k$$$ таких что $$$a_i<a_k<a_j$$$ или $$$a_i>a_k>a_j$$$ или $$$a_j>a_i,a_k$$$ или $$$a_j<a_i,a_k$$$, вычитаешь из ответа. Всё можно сделать поддерживая 4 ДО
В F действительно пишешь эту динаму dp[v][k] — минимальная цена сделать k вершин в поддереве v величины med+1. Внутри рюкзаком собираешь ответы по сыновьям, а потом вспоминаешь, что это работает не за куб, а за квадрат (как в barricades из looking for a challenge).
B?
Считаем динамику dp[i][j], прошли первые $$$i$$$ точки, и сейчас у нас в живых $$$j$$$ чуваков, которые летят вправо.
Пересчет, если $$$i$$$-й летит направо, то dp[i][j] = dp[i-1][j-1], иначе dp[i][j] = dp[i-1][j] с вероятностью 1/2, если самый правый из прошлых уничтожил нас, когда мы встретились, или dp[i][j + 1] с вероятностью 1/2, если мы уничтожили самого правого из предыдущих j+1.
Привет! Не совсем понятно, поясни, пожалуйста:
1) откуда берётся $$$dp[i][j + 1]$$$
2) как учитывается ситуация, когда какой-то из чуваков полетел влево, всех прибил, развернулся и полетел назад