Я перебирал циклический сдвиг. Дальше решал задачу для отрезка динамикой z[i][j] — где стоим и сколько должны начиная с нашей позиции выкинуть.

Посмотрим на итоговый ответ. Понятно, что в нём будет такое i, что среди i + 1, ..., i + l_i - 1 нет взятых в ответ элементов (в начальной конфигурации; просто возьмём какой-то элемент и пойдём от него направо, пока не упрёмся в требуемый, круг мы сделать не можем). А значит, перебираем элемент-"разрез" и проходимся тупой динамикой с конца разрезанного круга.

Можно просто выбирать набор карточек с сумой уровней не больше n, c максимальным уроном.

Рюкзак, где вес вещи — l_i, а стоимость — d_i. Нужно набрать вещей с суммарным весом не более N.

У меня другое чувство, когда на третью уходит меньше времени, чем на вторую :(

UPD: А потом еще другое чувство, когда видишь решение в две строчки по 500

Расскажу свое решение, не претендую на оптимальность асимптотики и времени написание кода. :) Придумал на раунде, но написать не успел и досдал только что в практисе.

Рассмотрим нашу решетку как детерминированный конечный автомат над алфавитом {L, R, U, D}. Состояниями будут вершины сетки, в которых нет препятствия, а также будет сток, который будет допускающим состоянием. Переходы из состояния по каждой букве ведут в ту вершину, куда сместилась бы монетка на этой позиции при заданном действии. Если она падает со стола, направим ребро в сток.

Когда положение монет хорошее? Когда есть 2 монеты, которые лежат на неэквивалентных состояниях (ибо есть различающая их строка, а значит, одна упадет, а другая -- нет). Посчитаем, сколько таких расстановок (точнее, посчитаем все и вычтем плохие). Плохие — это когда монетки лежат на позициях, соответствующих эквивалентным состояниям. Вычтем в таком случае из ответа 2^cnt - 1, где cnt -- количество вершин в каком-то классе эквивалентности. Итого, , где cnt_i — количество вершин в i классе эквивалентности вершин в автомате, и .