268A - Матчи

При ограничении в 30 команд самое простое решение заключается в симуляции всех поединков:

for i = 1 to N
  for j = 1 to N
    if i != j and h[i] = a[j] then
      ++ans

Существует также решение, работающее за O(N + M), где M — длина диапазона номеров цветов (то есть 100 при данных ограничениях). Для начала нужно посчитать для каждого цвета i количество команд cntH[i], у которых домашняя форма цвета i, и количество команд cntA[i] с выездной формой цвета i. Ответ задачи — сумма произведений этих количеств для каждого отдельного цвета, то есть сумма cntH[i] * cntA[i] по всем i.

268B - Кнопки

Для начала озвучим наихудший сценарий. Более-менее очевидно, что в худшем случае при угадывании i-ой (1 <= i <= n) по счёту кнопки Манао должен допустить n-i ошибок, потому что после этого становится понятно, какая кнопка правильная.

Посчитаем, сколько в сумме нажатий потребуется Манао прежде, чем он поймёт, какая именно последовательность кнопок правильная. При угадывании первой кнопки он допускает n-1 ошибку, но "цена ошибки", то есть на сколько кнопок нужно нажать чтобы её допустить, равна 1 нажатию. При угадывании второй кнопки цена ошибки уже 2 нажатия, потому что каждый раз приходится набирать первую (уже известную) кнопку. Продолжая в том же духе, получается что при угадывании i-ой по счёту кнопки Манао сделает (n-i) * i нажатий.

После того, как Манао понял правильную последовательность, ему остаётся её один раз ввести, что требует ещё n нажатий.

Отсюда получается алгоритм за O(n): просуммировать (n-i)*i для i=1, ..., n-1, и добавить к полученному числу n.

При значениях n, которые не выходят за диапазон 32-битных целых чисел, можно решать задачу и за O(1)*. Раскроем сумму (n-i)*i = n*i - i*i. Сумма первых слагаемых — это n*(1+...+n-1), где нам поможет сумма арифметической прогрессии. Сумма вторых слагаемых — это сумма квадратов от 1 до n-1, что вычисляется с помощью кубического полинома: http://pirate.shu.edu/~wachsmut/ira/infinity/answers/sm_sq_cb.html

*Единственная проблема — что ответ при больших n не умещается даже в 64-битный целый тип данных, но можно например вычислять его остаток при делении на что-нибудь.

268C - Красивые множества точек

Очевидно, что когда в множестве есть некоторая точка (x', y'), в нём не может быть никакой другой точки с x=x' или y=y', потому что тогда между этими двумя точками обязательно было бы целое расстояние. Есть всего n+1 различных x-координат и m+1 различных y-координат. Соответственно, размер искомого множества не может превосходить min(n, m) + 1.

Без условия x+y>0 нам бы подошло множество из точек (i, i) (0 <= i <= min(n, m)). Расстояние между точками (i, i) и (j, j) равно |i-j|*sqrt(2) и может быть целым только при i=j. С другой стороны, таких точек min(n, m) + 1, а мы уже знаем, что больше взять невозможно.

Раз точку (0, 0) использовать нельзя, сменим "диагональ": будем использовать точки (i, min(n, m) - i).

268D - Шведская стенка

Те, кто хорошо знаком с динамическим программированием, могут скроллить сразу вниз до "Итогового решения". Те, у кого есть некоторый опыт в этой теме, могут почитать мою попытку объяснить, как дойти до итогового решения. У кого опыта нету, тем наверное большого смысла это читать нету :)

Представим себе решение, которое перебирает все возможные дизайны, постепенно добавляя ступеньки снизу вверх. Например, допустим что оно уже выбрало направления для первых 10 ступенек и они вот такие: 2123412413 (то есть первая палка торчит в направлении 2, вторая — в направлении 1 и так далее). Теперь есть четыре варианта продолжить эту последовательность, приписав к ней '1', '2', '3' или '4'. Для каждой из 4^n стенок-строк нам нужно проверить, что для хотя бы одного символа выполняется следующее условие: первое его вхождение в строку не дальше позиции h, каждое следующее отстоит от предыдущего не более чем на h позиций, а последнее далее позиции n-h.

Естественно, такое решение при больших значениях n за разумное время не работает, но от него можно оттолкнуться в поисках лучшего подхода. Заметим, что проверку строки можно делать при добавлении каждого нового символа: если оказалось, что где-то посередине строки для всех четырех символов нужные условия уже не выполняются, то не имеет смысла перебирать её до конца. Также заметим, что нам не нужна вся строка для того, чтобы проверять при добавлении символа выполнение условий. Достаточно лишь знать, когда в последний раз встретился каждый из символов '1', '2', '3' и '4', и выполнялись ли для них условия до сих пор. Но тогда получается, что два префикса, у которых [каждый из символов в последний раз встретился на одних и тех же позициях] и [для каждого из символов выполнение/невыполнение условий совпадает], абсолютно эквивалентны с точки зрения дальнейшей работы такого перебора. То есть например при h=4 следующие два префикса можно окончить (то есть дополнить их до любой длины n) равным количеством способов:

44123424132
12424224132

Последний раз каждый из символов встретился на одной и той же позиции, символы '1' и '3' для обеих строк уже "потеряны", то есть условия для них уже не выполняются, а символы '2' и '4' ещё могут обратить строку в удовлетворительную.

На основе сделанных наблюдений уже можно построить полиномиальный алгоритм, основанный на принципе динамического программирования. Пусть ways[curN][i][j][k][l][ii][jj][kk][ll] будет количеством дизайнов стенки, в которых есть curN штук ступенек, последняя ступенька, торчащая в направлении 1, была на высоте i, в направлении 2 — на высоте j и так далее; ii, jj, kk, ll — boolean переменные, обозначающие, выполняются ли до сих пор условия для ступенек в соответствующих направлениях. Направив ступеньку на высоте curN+1 в одном из направлений, мы получим дизайн с curN+1 ступеньками, где эта последняя ступенька будет на высоте curN+1, а другие останутся на своих местах. Выполнение условий тоже можно и нужно пересчитать. Учитывая, что curN всегда равен одному из {i, j, k, l}, можно получить алгоритм со сложностью O(n^4). Так как это слишком медленно, подробно его разбирать не стану.

Сделаем следующее наблюдение: если мы сейчас рассматриваем палку на высоте curN, а последняя палка в некотором направлении была раньше чем curN-h палок назад, то нас не интересует, на какой конкретно высоте она была — это направление уже непригодно. Получается, что количество состояний в нашем алгоритме можно сделать порядка O(n*h^3). Более того, параметры, отвечающие за выполнение условий в каждом из направлений, коррелируют с высотами последних ступенек в этих направлениях, так что при желании от них можно (почти) избавиться, уменьшая количество состояний ещё в несколько раз.

На основе сделанных наблюдений можно наверное построить в некоторой степени разные решения, я расскажу своё.

Итоговое решение

Как ни странно, давайте заведём пятимерную динамику :) Пусть ways[curN][alive][last1][last2][last3] будет количеством таких дизайнов, где:

• Ровно curN ступенек

• Если то направление, в котором торчит последняя ступенька, всё ещё "живое", то alive = 1, в противном случае 0. Живое направление — это в котором первая ступенька была не выше h, а каждая следующая была не больше чем на h над предыдущей.

• last1, last2 и last3 содержат информацию об остальных трех направлениях. Направления никак не пронумерованы. lasti = 0 в двух случаях: если в соответствующем направлении ступенек не было вообще, или если последняя была более чем h ступенек назад. В остальных случаях в lasti записано, сколько ступенек назад была ступенька в этом направлении, то есть разница между curN и высотой последней ступеньки в данном направлении.

В целях оптимизации можно иметь last1<=last2<=last3, что уменьшает количество состояний примерно в 6 раз. Тем не менее, это усложняет код и в этой конкретной задаче особого выигрыша не давало (потому что обработка переходов стала более долгой). Переходы я буду рассматривать без учета данной оптимизации.

Теперь рассмотрим обработку переходов из конкретного [curN][alive][last1][last2][last3]. Обрабатывать состояния мы будем в порядке от curN = 1 до curN = n-1. ways[1][1][0][0][0] (то есть поставлена лишь первая ступенька) положим равным четырем, как базисный случай. Так вот:

• Если следующей мы ставим ступеньку в том же направлении, что и последняя (та, что на высоте curN), то мы грубо говоря получаем состояние [curN+1][alive][last1+1][last2+1][last3+1]: curN увеличилось на 1; направление, в котором поставили последнюю ступеньку, если было "живое", то определенно так и осталось и не могло "ожить" если не было; все lasti увеличились на один. Тут надо уточнить, что если lasti было равно 0, то его увеличивать нельзя (этой ступеньки или не была, или была но слишком давно). Также надо уточнить, что при lasti=h-1 оно превращается в 0 (последняя ступенька уже слишком низко).

• Если следующей мы ставим ступеньку в направлении, где последней была ступенька на высоте last1, то получаем состояние [curN+1][last1 > 0 || curN < h][alive][last2+1][last3+1]. Расшифровка: если last1>0, тогда это направление "живое". Также last1 может быть 0, но количество имеющихся ступенек быть меньше h — тогда это может быть лишь первой ступенькой и поставив её, мы будем иметь "живое" направление. На месте направления, за которое отвечал параметр last1, теперь то, в котором смотрела последняя ступенька. Соответственно, она была 1 ступеньку назад и надо написать там [1]. Но возможно, что это направление уже было мертвое и тогда надо написать [0]. Получается, что оно совпадает со старым значением alive. last2 и last3 меняются как и в прошлом пункте.

• Направления last2 и last3 обрабатываюся аналогично направлению last1.

Когда мы переходим по переходу этой динамики, новому состоянию добавляется количество вариантов, которым получалось старое. Итоговый ответ — сумма по всем [n][1][a][b][c], где 0<=a,b,c<h, плюс сумма по всем [n][0][a][b][c], где хотя бы одно из a, b, c ненулевое. Таким образом, у нас есть алгоритм со сложностью O(n*h^3), которому нужно асимпотически столько же памяти. Если его неаккуратно реализовывать (особенно на Java), то он словит ML. Лечится это дело несложно: так как для вычисления значений [i][][][][] нужны лишь значения [i-1][][][][], можно в любой конкретный момент запоминать лишь O(h^3) состояний.

Да уж, до написания разбора она мне такой громоздкой не казалась :)

Можете посмотреть решение пользователя SteamTurbine: 3027309, там довольно компактная реализация похожей идеи.

268E - Плейлист

Для начала давайте найдём ответ для фиксированной последовательности песен. Рассмотрим любые две песни, которые стоят в плейлисте на местах i и j, i < j. Если Манао понравилась песня i и не понравилась j, то произойдёт повторное прослушивание песни i. Соответственно, длина процесса с вероятностью p[i]*(1-p[j]) увеличится на L[i]. Сумма L[i]*p[i]*(1-p[j]) по всем парам (плюс сумма всех длин песен, потому что Манао их один раз послушает точно) и есть мат. ожидание для фиксированного порядка.

Получается, что из двух песен (l1, p1) и (l2, p2) следует поставить раньше первую, если l1*p1*(1-p2)>l2*p2*(1-p1), и вторую в противном случае. Если у нас всего две песни, то это очевидно. Если у нас есть ещё песни, то можно сказать — а вдруг, несмотря на то что это неравенство выполняется, есть ещё третья песня (l3, p3), для которой с первой песней неравенство определит, что надо её ставить до этой первой, а для второй — что после второй? Тогда было бы непонятно, какой из порядков даёт максимальное мат.ожидание. Посмотрим на этот случай пристально:

l1*p1*(1-p2)>l2*p2*(1-p1)
l1*p1*(1-p3)<l3*p3*(1-p1)
l2*p2*(1-p3)>l3*p3*(1-p2)
<=>
l1*p1/(1-p1)>l2*p2/(1-p2)
l1*p1/(1-p1)<l3*p3/(1-p3)
l2*p2/(1-p2)>l3*p3/(1-p3)

(Тут я закрыл глаза на факт, что p[i] могут быть равны 0 или 1, но это не важно)

Что за фигня, у нас противоречие! Видимо таких случаев не бывает :)

Далее, рассмотрим некоторый порядок песен (l[1], p[1]), ..., (l[n], p[n]), где существует пара соседних песен i и i+1, для которых не выполняется l[i] * p[i] * (1 - p[i + 1]) >= l[i + 1] * p[i + 1] * (1 - p[i]), и допустим, что этот порядок оптимален. Очевидно, что при замене местами песни i и i+1, ответ изменится на ту величину, которую в него вносила именно эта пара песен (имеется в виду величина l[i] * p[i] * (1 - p[i + 1])). Все остальные песни остались относительно каждой из песен i и i+1 в том же порядке. Но мы имеем l[i] * p[i] * (1 - p[i + 1]) < l[i + 1] * p[i + 1] * (1 - p[i]), значит, поставив песню i+1 перед песней i, мы получим большую величину. Таким образом, получаем противоречие — изначальный порядок был неоптимален.

Получается, что надо всего лишь упорядочить песни по убыванию l[i]*p[i]/(1-p[i]) для достижения перестановки с максимальным мат.ожиданием. Осталась проблема вычисления ответа для конкретной перестановки: до сих пор мы это умели делать только за квадрат, что при n=50000 многовато. Тут можно использовать идею, которая наверное тоже в какой-то мере является примером динамического программирования. Допустим, мы зафиксировали j и считаем, сколько песня j добавляет к ответу, если Манао она не понравится. Это величина (l1*p1 + l2*p2 + ... + l[j-1]*p[j-1]). Для j+1 аналогичная величина будет иметь вид (l1*p1+...+l[j-1]*p[j-1]+l[j]*p[j]). Раз эти величины отличаются на 1 слагаемое, можно их пересчитывать за O(1), если рассматривать j один за другим по возрастанию. Идею вычисления ответа для фиксированной перестановки можно выразить вот так:

lovedLenExp = 0.
answerExp = 0.
for j = 1 to N
  answerExp += l[j]
  answerExp += lovedLenExp * (1 - p[j])
  lovedLenExp += l[j] * p[j]

Вот в принципе и всё :)