А у нас (в Intel.ru), похоже, новшество - впервые не появился перевод очередного задания. А я уже предвкушал увидеть свежую оригинальную словоформу для перевода термина graceful graph :) Что ж, придется разочарованно сообщить, что проблемы в переводе нет - так и переводится "грациозный граф" - см. известную книгу: А.А.Зыков, Основы теории графов, М.: Вузовская книга, 2004, С. 558. А вот с решениями могут быть проблемы: судьи разрешили использовать эвристические алгоритмы (см. американский форум). Исчерпывающее и даже сколь-нибудь полное тестирование такого алгоритма, особенно в рамках временных ограничений конкурса, невозможно, а доказательства по определению не существует. Довод, прозвучавший на американском форуме, что эвристическое решение сильно рискует получить штрафные баллы, не успокаивает. Для многих возможных эвристик слишком мала вероятность выявления неправильной работы на сильно ограниченном наборе тестов (так что рискует, но только теоретически!). Таким образом, очень возможно, что победу, по условию, одержит быстрое, но в целом некорректное решение... Задача поставлена в общем интересная, а вот сформулирована, как некоторые предыдущие. Жаль все же, что нет перевода - здесь уже было, что, обсуждая перевод, мы выходили на обсуждение формулировки самой задачи.
--Михаил (mt2).
PS(ЗЫ)Добавляю недостающие смайлики, просьба расставить по желанию ;))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))
