https://ru.m.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%B2%D0%B5%D1%80%D1%88%D0%B8%D0%BD%D0%BD%D0%BE%D0%BC_%D0%BF%D0%BE%D0%BA%D1%80%D1%8B%D1%82%D0%B8%D0%B8

Реально чмом чувствую т.к. должно быть простое решение

Спасибо огромное. Гляну

Это вроде задача о вершинном покрытии, она np-полная

разве?

Насколько я понимаю, там нет решения сильно проще перебора

вот тут вершинное покрытие вроде как {0, 1, 2, 4}

а в задаче про кольца было бы 1,2,4

Неа

а стоп

1, 3

туплю

С независимым множеством путаешь

да да

это просто не минимальное

Я вроде покрытие умею решать за 2^n * n

можете накидать примеров для проверки break rings?

Нормального материала "для новичка" не смог найти в инете. Пока непонятно, хотя вроде как жадный алгоритм применял и он не подошёл. Наверное тупой вопрос, но что стоит почитать чтоб втянуться?

Ща

Блин. Я покидаю, но завтра утром

:(

а ты где их взял? там же

?

Там встроенных штук 20

Показаны лишь 3 вроде

и как их увидеть?

хотя бы три

Ну как. По той ссылке кликаешь и внизу справа solve it

Хотя мб для этого нужно зарегаться на том сайте

видимо да

Если не пройдешь какой либо тест - сможешь его посмотреть

Только 1 минус - через тф не грузит. Только пк

:/

Ага.

Ленивый алгоритм понял как работает?

в данной задаче?

Вообще принцип. Везде где искал понял только что он перебором удаляет рёбра (по 2 вершины) и выдаёт минимум решения

Минимум вырезанных

а зачем думать ребрами

Жадный срывается, когда кольца выглядят примерно так:

бл, писал в repl.it, теперь TabError

Ну по вершине вариант думаю, только долгий боюсь получится

Что за repl.it?

Никакой жадный тут не заработает, если у них не паленые тесты

Ну такой тест вроде последний

Его мой жадный алгоритм и не прошёл

Завтра попробую переписать через перебор. Других вариантов не вижу

Один минус - будет долгий до жопы

Сколько там колец?

Там и по 17 колец есть.

Это мало

Но по моему не больше

За секунду успеет

Хотя может и нет

Это ж питон

Вариантов получится 17! Вроде?

C++ бы точно успел

Ну ёпт)

Неа, можно быстрее

Каким образом перебором и меньше?

Можно сделать динамику по подмножествам

Это как

Храним маски из 0 и 1 - используем мы это кольцо или нет

Матрица?

Каждой маске соответствует ответ

Массив из 2^17 скорее

ERROR: S client not available

И потом по очереди пытаемся добавлять

Перебором разве не быстрее?

Перебор это факториал, а тут экспонента

Не очень понял как при этом учитывать рёбра

Я чё т туго соображаю. Не совсем понимаю твой алгоритм

Но экспонента явно лучше факториала

Ща может в гугле найду

Ок. Спасиб

Вообще самый простой способ - перебираешь все маски и пробуешь каждую

То есть смотришь каждый вариант

Я не совсем понял твой варик с масками. Каким образом они учитывают рёбра

Берешь какой-нибудь вариант и смотришь, верно ли, что для каждого ребра выбрана хотя бы одна вершина

...

Ребро состоит из 2 вершин. Моя непонимать

Допустим, у тебя 10 вершин

Да

Предположим, что ответ (1, 2, 3, 5)

Да

Пройдемся по списку ребер и посмотрим, верно ли, что у каждого ребра хотя бы одна вершина есть в этом списке

Если у какого-то нет, звено осталось неразорванным и ответ не подходит

В списке из эих 4х вершин?

Да

Правильно ли я понял - вместо перебора вариантов с их 17! Вариантами проще перебрать ответы с их меньшим кол-вом вариантов?

Да

?

хех, хитро

Если перебрать все возможные варианты, будет 2^17

Попробую завтра. Спасибо за идейку

Меньше

Каждое либо берем, либо нет

Можно по возрастанию. Сначала из 1, потом из 2х, после из 3х

И если находится какая либо