|
|
|
|
|
|
|
Вернуться
| 1 Лукьянов Иван, 09 сентября 2018 г. 23:12:41 | |
|
Фёдор Владимирович, если такая задача получит сложность 96 %, то что же будет за задача со сложностью 99 или 100 %? :)
|
|
|
| 2 Демиденко Виталий, 29 августа 2018 г. 1:04:09 | |
|
Вообще, кто не знает, эта задача с нашего прошлого четвертьфинала ACM ICPC, проходившего в Красноярске. Я в нём тогда участвовал, помню, и автора знаю. Он тогда после контеста подтвердил, что накосячил. И на сборах в Петрозаводске с нас смеялись, что мы уже на чфе NP-полные задачи решаем (крутой регион). То есть, не я это начал.
|
|
|
| 3 Демиденко Виталий, 29 августа 2018 г. 0:57:56 | |
|
Это задача найти хроматическое число графа, прямо так и гуглить можно (или Graph coloring). Животные = вершины, клетки = цвета. Является NP-полной.
|
|
|
| 4 Хворых Павел, 28 августа 2018 г. 16:03:08 | |
|
Фёдор Владимирович, это в точности задача о кликовом покрытии, где ребра соединяют совместимых животных.
|
|
|
| 5 Меньшиков Фёдор Владимирович, 28 августа 2018 г. 15:12:28 | |
|
Если обоснуете - то неплохой вариант как с задачей Ships. Version 2 архива acm.timus.ru: подобрать тестов посильнее. И находить решения через эвристики. А потом заваливать прошедшие эвристики. Рейтинг 96% этой задаче тогда вполне можно было бы дать.
|
|
|
| 6 Меньшиков Фёдор Владимирович, 28 августа 2018 г. 15:03:23 | |
|
Обоснуйте NP-полноту.
|
|
|
Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!
| | | |
