Комментарии 12
Вот спасибо)) Как раз искал какие-нибудь задачки) А тут еще и на новогоднюю тематику! =)
0
Это было жестоко… Уже 3ий день не могу оторваться от задач. Сложные, местами, но затягивают. А система проверки решения — вообще нечто.
0
Попробуйте еще наш формат ru.hexlet.io/games ;)
0
Да, странно, что до сих пор не было поста. Участвую с первого дня, задачки забавные. Изредка даже удаётся в Leaderboard попасть.
0
Нет, подход «реши простые задачки, тогда откроем сложные» — это не очень интересно. Приятнее идти от самых трудных.
0
Кстати, вторая задача про молекулу была NP-полной, или только квазиполиномиальной?
0
Да, NP-полная, насколько я понимаю. И вообще на самом деле это порождающая грамматика Хомского.
О решении усложнённой задачи про молекулу
В задаче про то как из e надо получить длинную молекулу я действовал полным перебором, но не пытаясь построить молекулу от е, а наоборот, пытаясь сократить результирующую молекулу до е, применяя правила в обратном порядке. Если при этом добавить некоторое количество «жадности» алгоритму, то есть сначала «сворачивать» максимально длинные подцепочки, то результат получается за какое-то совершенно смешное количество итераций. Мне интересно, а как другие её решали?
0
Скрытый текст
Я тоже шёл в обратную сторону. Но оказалось, что жадный алгоритм быстро попадает в тупик и не может из него выбраться. Анализ показал, что тупиком является цепочка CaRnFAr, перед которой не идёт атом Th (и возможно, несколько атомов Ca). После того, как я запретил эти цепочки, алгоритм быстро что-то нашёл.
0
Зарегистрируйтесь на Хабре , чтобы оставить комментарий
Advent of Code