Блог пользователя e-maxx

Автор e-maxx, 14 лет назад, По-русски
Расскажу авторское решение этой задачи.

Решение методом динамического программирования: состояние - это пара (pos, pref), где pos - позиция в набираемой нами строке-ответе (т.е. от 0 до n), а pref - текущий набранный префикс образца P (т.е. это число от 0 до length(P)). Значение pref будет помогать нам контролировать вхождения образца P: если pref = length(P), то это означает, что в этом месте оканчивается очередное вхождение образца P (а начиналось это вхождение в позиции pos - length(P)).

Значение динамики равно true, если это состояние достижимо. Мы стартуем из состояния (0, 0) и хотим прийти в состояние с pos = n.

При этом в самой динамике мы делаем такие переходы: мы перебираем очередной приписываемый к ответу символ C, и переходим в состояние (pos + 1, newpref), где newpref - это новая подсчитанная длина набранного префикса. Ограничения позволяли пересчитывать это значение newpref втупую, т.е. просто ища в строке P подстроки вида P[length(P) - oldpref..length(P)] + C.

Например, если P = ab, и pref = 1, то при переходе по C = a мы перейдём в newpref = 1 (т.к. к строке a приписали букву a - и получилась aa, но у неё наидлиннейший суффикс, совпадающий с префиксом P, равен a. А вот при переходе по букве C = b мы перейдём в состояние newpref = 2. При переходе по любой другой букве мы перейдём в состояние newpref = 0.

Но на самом деле, конечно, здесь угадывается алгоритм префикс-функции: мы фактически отвечаем на запрос "у нас был набран какой-то префикс образца P, и к нему добавили один символ C - какой будет новый префикс"? На такие запросы как раз и отвечает префикс-функция, и более того, ответы на все такие запросы (запрос - это пара (pref, C)) можно посчитать заранее и брать из таблички (это называется автоматом по префикс-функции).

Так или иначе, если мы смогли посчитать значение newpref, то дальше всё становится просто: мы умеем делать переходы в динамике, потом нужно будет только восстановить по динамике ответ.

Если искать newpref самым кошерным способом - с помощью автомата по префикс-функции, то решение получается за асимптотику O(kn2), но, повторюсь, в задаче проходили решения и с худшими асимпотиками (чтобы не усложнять эту задачу чрезмерно).


P.S. Эта задача интересна тем, что по ней можно придумать всякие нечёткие решения, которые наверняка прошли у участников этого контеста. Одно из таких простых решений, которое не удалось завалить даже спустя пару суток стресса, я напишу чуть позже в комментах.
Разбор задач Codeforces Beta Round 50
  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится
А точно оценка O(n2k) ?) Как-то много получается)

  • 14 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Хаха )) Исправил ) Это тут кривенький TeX-парсер стоит
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Тут есть TeX-парсер?

      • 14 лет назад, # ^ |
          Проголосовать: нравится +10 Проголосовать: не нравится
        Ну да, он доступен и в постах в блоге, и в комментариях. Просто между долларами записываешь выражение - и всё. Дело в том, что насколько я знаю, все существующие TeX2HTML-парсеры довольно кривые и неудобные в использовании. В общем так или иначе, но codeforces использует свой велосипед для этого, а велосипед этот поддерживает только самые основные вещи TeXа )
14 лет назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится
Вот это решение 246049??? от bahakz
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    da reshenie. nujno vstavit stroku vezde gde stoiat 1. ostalnie bukvi zabit libo pervoi bukvoi libo poslednei, esli netu bukvi kotoraia ne vstrechaetsia v stroke
14 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
Можно просто за O(n), используя префикс функцию :)
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Ну вот у нас есть за O(n), но только это нечёткое решение, которое я анонсировал :)

    Решение такое: ну, понятно, поприкладывать паттерн P там, где стоят единички. Дальше надо чем-то заполнить оставшиеся позиции. Вот, и утверждается, заполнять надо любой буквой, отличной от P[preffunc[length(P) - 1]], т.е. любую букву, отличную от той, которая идёт после длиннейшего префикс-суффикс совпадения.

    Например, P = "aba". Тогда заполнять пустоты можно любой буквой, отличной от "b".


    Почему это - я долго пытался доказать или опровергнуть, но моего владения префикс-функцией оказалось недостаточно :) Стресс, как я уже говорил, тоже не смог обломать это решение.

    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Оставшиеся позиции, можно было заполнять перебором с отсечениями. перебор от 2х параметров pos и маски тех позиций, начиная с которых образец не должен встречаться (нолики из битовой маски из входных данных), и которые ище небыли удовлетворены. Понятие "удовлетвореная позиция" означает то, что мы уже ранее поставили какой-то символ таким образом, что вхождение образца уже гарантировано не будет в этой позиции. 

      Ссылку на это свое решение стыдно кидать по многим причинам, но кому уж очень интересно смогут найти сами :-[

14 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
why your editorail for contest 50 is writen to russia ?

please put this to english in your blog

thanks , very nice problem's ....
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Переборное решение проходит за 30 мс. Был уверен, что это авторское и долго ругался. Как выяснилось, зря:)
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Честно говоря, не понял приведенного решения. Не придумал, что делать после того, как мы получили все возможные переходы (pos,pref)->(pos',pref'), т.е. как задействовать фигурирующий в условии битовый массив, обозначающий вхождение образца.
На дорешивании сдал следующее решение - накладываем образец на строку там где указано, потом пытаемся заполнить пробелы - последовательно от начало до конца ставим символ в очередное свободное место, такой, чтобы значение префикс-функции в этой позиции было минимальным.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Ну фактически дальше, после того как мы посчитали все такие переходы, мы делаем обход в ширину: стартуем из (pos=0, pref=0), и хотим прийти в (pos=N).

    Как мы учитываем маску? Мы каждый раз при выполнении перехода смотрим на получающееся значение pref: если оно равно length(P), то надо, чтобы в маске pos-length(P)-ый бит был равен '1', а иначе - он должен быть равен '0'. Если это условие не прошло - то соответствующий переход в динамике (или обходе в ширину, как угодно это называть) запрещаем, иначе разрешаем.