в Б. посортим массив B. потом динамика dp[i][lf][rg][k] — макс ко-во очков если мы поставили i первых чисел из A, lf наименьших и rg наибольших чисел из B, k = 0..1 — последнее число перевернуто или нет.

E: заметим, что фишки могут занимать всего n = 21 различную позицию, а также то, что самая правая из фишек никогда не движется влево. Состояния будем записывать как (i, j), где 0 ≤ i ≤ j < n.

Тогда просуммируем (по линейности матожидания сумма будет ответом) такие величины: — ожидаемое число ходов до попадания из (0, 0) в (0, 1), а также для i от 2 до n — ожидаемое количество ходов до попадания из (i - 2, i - 1) в (i - 1, i) (легко заметить, что через любое из этих состояний надо пройти).

Заметим, что в каждом конкретном слагаемом можно считать одну фишку неподвижной, а другую движущейся, что даёт систему из i уравнений на i переменных: x_k — матожидание времени попадания из (k, i - 1) в (i - 1, i) 0 ≤ k ≤ i - 1. Для них можно составить уравнения вида x_k - p·x_{max(k - 2, 0)} - (1 - p)·x_k + 1 = 1, где x_i положим равным 0. Нужно найти x_i - 2. Для этого решим систему Гауссом.

Итого, находим n слагаемых, каждое за O(n³), итого O(tn⁴).

B: M фишков есть отсортированных; между два из N фишков не нужно дать более одного из M фишков. Динамическое программование: dp[x][i][j][k] = первых j и последних k из M фишков добавленных пред i-й из N (который есть перевёрнут — x = 1, или нет — x = 0). Кроме стандартных транзиций (dp[0][i][j][k] = max(dp[0][i - 1][j][k], dp[1][i - 1][j][k]), dp[1][i][j][k] = dp[0][i - 1][j][k] + F[i]) можно добавить максимальную фишку между i и i - 1 (или пред i = 1) и перевернуть ее (dp[0][i][j][k] не меньшее dp[0][i - 1][j][k + 1] + P[k]) или минимальную и не перевернуть (dp[1][i][j][k] не меньшее dp[1][i - 1][j + 1][k] + F[i]). Если остаются фишки из M, даем их за N-ю жадным алгоритмом. Сложность: O(NM²).

Screencast

Как решать F?

Как С решается?

А кто-нибудь знает, где Series standings можно посмотреть, а то на самом снарке результаты от предыдущей серии?