Весьма интересно, если правда; но весьма непонятно, как вообще что бы то ни было может снять необходимость в регистрации на двух сайтах, если без регистрации на icpc.baylor.edu в принципе нельзя участвовать в ACM ICPC, а без регистрации на icpc.org.ua в принципе неоткуда взяться таким полям, как "украиноязычное написание имени" и "номер студенческого билета". В любом случае прошу snarknews прокомментировать, если он считает нужным.

Нормально; он меняется на Accepted вручную координатором 1-го этапа, и это может быть очень длительный процесс.

1. Пройдем справа налево и каждой букве X поставим в пару первую свободную букву Y слева. Отсортируем полученный набор пар по позиции буквы Y. Можно доказать, что если существует ответ из k слов, то существует ответ, в котором индексы последних двух букв каждого слова являются одной из k последних пар в полученном наборе.

2. Теперь сделаем бинарный поиск по ответу. Пусть мы хотим проверить, можно ли вырезать k слов. Оставим k максимальных пар из построенного набора и попытаемся поставить им в соответствие первую букву. Сделать это можно жадно: пройдемся слева направо по всем парам и для очередной пары поставим в соответствие самую левую, невзятую букву X или Z. Если для какой-то пары такой буквы не нашлось, то ответ на проверку "нет".

Что-то не наблюдаю я тут центр(upd: уже нашел)

Динамика.

Пусть dp[i][j] — это минимальное кол-во знаков '+' в строке состоящей из первых i символов исходной строки a образующей сумму j. dp[i][j] можно вычислить как минимум по k из dp[i — k][a[i-k+1..i]] + 1, где a[i-k+1..i] — число образованное подстрокой строки a c позиции i — k + 1 по i включительно — получается мы пытаемся вставить '+' между i — k и i — k + 1 символами. Перебирать все k не нужно, т.к. ограничение на общую сумму 5000, то достаточно перебрать k до 4-ех (еще нужно учесть что перед подстрокой могут быть лидирующие нули и обработать это, т.к. всегда выгодно поставить '+' перед лидирующими нулями).

Ответ(минимальное кол-во знаков '+') находится в dp[n][t], где n — длина строки a, а t — сумма которую необходимо получить. Чтобы восстановить ответ нужно вместе с dp[i][j] запоминать из какого состояния было обновлено значение динамики (позицию i-k).

Подозреваю, что пока что нигде. Черкасскую область я расшифровывал вручную; можете попробовать сделать то же для других областей Центра на основании http://194.105.136.86/center500.php и https://docs.google.com/spreadsheets/d/1303Q2_H5b30C22-1VMsXwWk10fbvEu4y5QpRDxPaOuk/edit?usp=sharing Для Киева у меня нет даже таких данных.

Сделал общую табличку по всем регионам (Запад, Восток, Юго-Запад, Киев) и с расшифрованными результатами центра. Если кто-то поделится расшифровкой киевских команд, смогу их тоже добавить.

UPD: Добавил все школьные команды и отметил их как внеконкурсные.

Спроси у Мицы он та шарит, он же тренер как никак двух команд финалистов.

Наши школьники стеком решали, за O(N)

Только надо равные значения обрабатывать как одно (просто держать число и количество таких в стеке)

G: https://ideone.com/GFWYym

Спасибо, что обратили внимание.

Насколько могу судить по тем результатам Черкасской области, которые выверял вручную, правильно на http://acmallukrainian.ho.ua/standings.html и неправильно на https://icpc.baylor.edu/regionals/finder/ukraine-central-2018/standings Что грустно, потому что именно на бейлоре должны быть официальные результаты.

Только моё личное мнение ещё не имеет никакой официальной силы. Если кто-то что-то может уточнить -- отпишитесь, пожалуйста.

Региональному координатору А.Л.Хиже я уже сообщил, но он в отъезде и не_может сегодня посмотреть.