How to become an author
Search
Write a publication
Pull to refresh

Comments 24

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


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

Total votes 2: ↑2 and ↓0+2

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


  1. Не 2^N, а (fi)^N, fi ≈ 1.618
  2. С помощью мемоизации (я ее в исходниках на нашел) можно добиться O(N) вызовов (тормозом будет вывод ответа)
  3. Динамика нужна по суффиксам, фактически у автора что-то очень близкое.
Total votes 1: ↑1 and ↓0+1
  1. Не понял, почему у вас основание экспоненты в О-нотации имеет какое-то значение.
  2. Мемоизации какой именно? Вызовов чего? Там в любом случае экспонента.
  3. Посмотрите, пожалуйста, код по ссылке ниже.
Total votes 2: ↑0 and ↓2-2
  1. А можете кинуть ссылку на док-во, что основание можно убрать? (я без сарказма)
  2. Экспонента конечно же да, но чуть быстрее станет.
  3. Код, конечно, хороший (и без оверинжиниринга автора), но асимптотически работает не быстрее.
This comment wasn’t rated yet0

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

Total votes 2: ↑0 and ↓2-2
Вы неправы. Константный множитель в показателе — это не то же самое, что константный множитель.

Например, 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).
Total votes 2: ↑2 and ↓0+2

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

Total votes 1: ↑1 and ↓0+1
Так как автор не выложил словарь, его результат воспроизвести довольно сложно, но вот этот код, написанный на С++ на коленке за несколько минут, будто бы в 250 раз быстрее. Там используется динамическое программирование и обход в глубину получающегося направленного ациклического графа.
This comment wasn’t rated yet0
Так и есть. Задачка — примерно из тех, что в приличных конторах люди решают на собеседовании за час. Ну, может, чуть сложнее. Не на час, а, скажем, часа на три. Откуда тут взялись «длительные перерывы между коммитами» и прочее — стало ясно лишь в конце: у автора совсем плохо с алгоритмами было, когда он начал писать эту задачу (не знаю, как сейчас), потому, разумеется Шлемиэлизм был устроен весьма качественный…

P.S. В ваши «несколько минут» я не верю. Полчаса — может быть, но таки на это больше 5 минут ушло, почти наверняка…
This comment wasn’t rated yet0
А потом говорят, что олимпиадное программирование кроме олимпиад нигде не востребовано. И появляются ребята вроде автора с подобными решениями.
Total votes 3: ↑2 and ↓1+1

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

Total votes 3: ↑2 and ↓1+1

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

Total votes 2: ↑2 and ↓0+2
Ну дык. Решал то её не олимпиадник. С другой стороны классический олимпиадник выдает такой код, который потом нигде использовать нельзя. Автор же пишет более-менее качественный код.

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

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

This comment wasn’t rated yet0
я в csvшке в исходниках на гитхабе смотрел — там с 113 по 118 временные названия

112, Uub, Ununbium
113, Uut, Ununtrium
114, Uuq, Ununquadium
115, Uup, Ununpentium
116, Uuh, Ununhexium
117, Uus, Ununseptium
118, Uuo, Ununoctium
This comment wasn’t rated yet0
А как получился 'NoNRePReSeNTaTiONaL' — нет же элемента L?
This comment wasn’t rated yet0
видимо промежуточный результат вычисления, так как далее идет окончательный вариант — NoNRePReSeNTaTiONAl
(нобелий азот рений фосфор рений селен азот тантал титан кислород азот алюминий)
This comment wasn’t rated yet0
Sign up to leave a comment.

Your account

Sections

Information

Services

Support
© 2006–2024, Habr