ДП, состояние (маска рассмотренных вершин, из какой вершины идем). проверить будет ли пересечение отрезка (i, j) с текущим множеством можно, если есть в маске 2 таких вершины , которые будут находиться на обоих путях между (i, j) в обходе многоугольника.

Там примеры вообще никакие. Они не проверяют на реверс строки, они даже не проверяют на поиск именно подстроки в широком значении этого слова (в примерах, в которых победа — совпадение вырождается до одной буквы).

Ну и еще это немного троллинг со стороны авторов. Некоторые не очень сильные, увидев оценку 275, начали писать всякую ересь. К примеру, различные хитрожо... понтовые динамики на 100500 параметров (левый край первого, правый край первого, левый край второго, правый край второго, реверснутость первого, реверснутость второго, чей ход, какая фаза луны, что я ел на завтрак).

Еще многие не обратили внимание, что в случае совпадения после хода второго игрока — все равно побеждает первый. Этого тоже нету в примерах. Т.е. если есть 123 32, то первый вырежет 1 и сделает 23 32. На самом деле это дальнейшая победа первого, но некоторые подумали, что второй будет делать ход в текущее число первого — и это не будет означать победу (т.е. они просто будут по кругу бегать друг за другом).

Чтобы некоторые написали динамику наверное :)