acmp.ru 826 Жизнь цвета индиго https://acmp.ru/index.asp?main=task&id_task=826 Сложность: 53%, т.е. вроде не очень сложная
Написал перебором всех вариантов лампочек. https://pastebin.com/fApRg9wX Конечно же получил time limit error, т.к. сложность получилась 3^50000
Не могу придумать алгоритм решения. Вроде граф можно упростить, если идти от патрона, в который можно вкрутить только лампочку одного цвета: Например B — BI — IV — IVB превращается в B — I — V — IB
Но в худшем случае упростить ничего нельзя: IVB — IVB — IVB — .... — IBV Пытался жадным алгоритмом выключать из дерева вершины I, которые имеют наибольшее число соседей I https://pastebin.com/6FPVStAR Алгоритм дает ошибки на некоторых раскладах.
Какой алгоритм здесь применим? Как решается такая задача?
У меня такая же проблема, ты смог найти решение ?