Я не понял, откуда автор взял линейную сложность своего алгоритма.
В худшем случае(все одно- и двух- буквенные обозначения в таблице есть) его алгоритм от строки длины
N будет вызываться со строками длины N-1 и N-2.
Это соответствует дереву вызовов при наивном вычислении чисел Фибоначчи, работающем за O(2^N).
Более того, уменьшить сложность O(2^N) нельзя, так как именно за такое время удастся вывести сам ответ.


Если посатвить задачу вида "найти любое разложение" или "подсчитать кол-во разбиений", то такая задача
легко решается за полиномиальное время динамикой по подотрезкам.

Немного исправлюсь.


  1. Не 2^N, а (fi)^N, fi ≈ 1.618
  2. С помощью мемоизации (я ее в исходниках на нашел) можно добиться O(N) вызовов (тормозом будет вывод ответа)
  3. Динамика нужна по суффиксам, фактически у автора что-то очень близкое.
  1. Не понял, почему у вас основание экспоненты в О-нотации имеет какое-то значение.
  2. Мемоизации какой именно? Вызовов чего? Там в любом случае экспонента.
  3. Посмотрите, пожалуйста, код по ссылке ниже.
  1. А можете кинуть ссылку на док-во, что основание можно убрать? (я без сарказма)
  2. Экспонента конечно же да, но чуть быстрее станет.
  3. Код, конечно, хороший (и без оверинжиниринга автора), но асимптотически работает не быстрее.

O(a^n) = O(e^(n ln a)), а почему константный множитель не играет роли, полагаю, вы и так знаете.

Вы неправы. Константный множитель в показателе — это не то же самое, что константный множитель.

Например, 2^n = o(3^n) («o» малое), поскольку (2^n/3^n) -> 0 при n->\infty. Иными словами, 3^n растёт сильно быстрее, чем 2^n :) Таким образом, 2^n = O(3^n), но 3^n не O(2^n).

С логарифмами — да, основание неважно: log_a(n) = ln(n)/ln(a) = C * ln(n).

Надо было таки не полениться в предел разложить. Признаю, ошибся.

Так как автор не выложил словарь, его результат воспроизвести довольно сложно, но вот этот код, написанный на С++ на коленке за несколько минут, будто бы в 250 раз быстрее. Там используется динамическое программирование и обход в глубину получающегося направленного ациклического графа.
Так и есть. Задачка — примерно из тех, что в приличных конторах люди решают на собеседовании за час. Ну, может, чуть сложнее. Не на час, а, скажем, часа на три. Откуда тут взялись «длительные перерывы между коммитами» и прочее — стало ясно лишь в конце: у автора совсем плохо с алгоритмами было, когда он начал писать эту задачу (не знаю, как сейчас), потому, разумеется Шлемиэлизм был устроен весьма качественный…

P.S. В ваши «несколько минут» я не верю. Полчаса — может быть, но таки на это больше 5 минут ушло, почти наверняка…
А потом говорят, что олимпиадное программирование кроме олимпиад нигде не востребовано. И появляются ребята вроде автора с подобными решениями.

Не вижу противоречия. Задача сама по себе олимпиадная.

Ну да. А вот решение – не очень. :)

Ну дык. Решал то её не олимпиадник. С другой стороны классический олимпиадник выдает такой код, который потом нигде использовать нельзя. Автор же пишет более-менее качественный код.

Я не хочу начинать новый флейм о олимпиадном программировании, поэтому просто озвучу своё видение проблемы: олимпиадное программирование per se действительно не востребовано. А вот олимпиадники которые умеют писать код промышленного качества — очень даже нужны.
Очень нерациональное решение. Я бы написал конечный недетерминированный автомат регулярки вида "\b(элементы таблицы через альтернативу)+\b" дополнив его тем, чтобы он для каждого из активных состояний сохранял в стек встретившиеся лексему(ее ID).
Это, кстати, хороший такой себе стресс-тест для движка регулярных выражений… Многие из них в подобных случаях вырождаются в такую экспоненту, что результата можно ждать столетиями…
Ну в «правильных» автоматах разрабатывается механизм приоритета состояний. Тогда максимальное число состояний будет константно и не будет превышать количества узлов автомата.
кстати для 113-118 уже есть окончательно утвержденные названия вместо временных «уну-чтототам»))
csvшку можно и обновить)

А там у автора в коде как раз есть и флеровий, и оганессий. Без них floccinaucinihilipilification не раскладывается.

я в csvшке в исходниках на гитхабе смотрел — там с 113 по 118 временные названия

112, Uub, Ununbium
113, Uut, Ununtrium
114, Uuq, Ununquadium
115, Uup, Ununpentium
116, Uuh, Ununhexium
117, Uus, Ununseptium
118, Uuo, Ununoctium

А он CSV там привёл шутки ради, массив имён в коде зашит.

А как получился 'NoNRePReSeNTaTiONaL' — нет же элемента L?
видимо промежуточный результат вычисления, так как далее идет окончательный вариант — NoNRePReSeNTaTiONAl
(нобелий азот рений фосфор рений селен азот тантал титан кислород азот алюминий)
Только полноправные пользователи могут оставлять комментарии.
Войдите, пожалуйста.