Комментарии 24
Я не понял, откуда автор взял линейную сложность своего алгоритма.
В худшем случае(все одно- и двух- буквенные обозначения в таблице есть) его алгоритм от строки длины
N будет вызываться со строками длины N-1 и N-2.
Это соответствует дереву вызовов при наивном вычислении чисел Фибоначчи, работающем за O(2^N).
Более того, уменьшить сложность O(2^N) нельзя, так как именно за такое время удастся вывести сам ответ.
Если посатвить задачу вида "найти любое разложение" или "подсчитать кол-во разбиений", то такая задача
легко решается за полиномиальное время динамикой по подотрезкам.
Немного исправлюсь.
- Не 2^N, а (fi)^N, fi ≈ 1.618
- С помощью мемоизации (я ее в исходниках на нашел) можно добиться O(N) вызовов (тормозом будет вывод ответа)
- Динамика нужна по суффиксам, фактически у автора что-то очень близкое.
- Не понял, почему у вас основание экспоненты в О-нотации имеет какое-то значение.
- Мемоизации какой именно? Вызовов чего? Там в любом случае экспонента.
- Посмотрите, пожалуйста, код по ссылке ниже.
- А можете кинуть ссылку на док-во, что основание можно убрать? (я без сарказма)
- Экспонента конечно же да, но чуть быстрее станет.
- Код, конечно, хороший (и без оверинжиниринга автора), но асимптотически работает не быстрее.
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).
P.S. В ваши «несколько минут» я не верю. Полчаса — может быть, но таки на это больше 5 минут ушло, почти наверняка…
Не вижу противоречия. Задача сама по себе олимпиадная.
Ну да. А вот решение – не очень. :)
Я не хочу начинать новый флейм о олимпиадном программировании, поэтому просто озвучу своё видение проблемы: олимпиадное программирование per se действительно не востребовано. А вот олимпиадники которые умеют писать код промышленного качества — очень даже нужны.
csvшку можно и обновить)
А там у автора в коде как раз есть и флеровий, и оганессий. Без них floccinaucinihilipilification не раскладывается.
112, Uub, Ununbium
113, Uut, Ununtrium
114, Uuq, Ununquadium
115, Uup, Ununpentium
116, Uuh, Ununhexium
117, Uus, Ununseptium
118, Uuo, Ununoctium
есть пулл реквест
А он CSV там привёл шутки ради, массив имён в коде зашит.
Разбиение слов на элементы таблицы Менделеева