elizarov


Блог Романа Елизарова


Previous Entry Share Next Entry
Добрался в Питер и слил TCO Round 3
elizarov
История с перелетом получила счастливый конец. А дождался представителей Lufthansa, они покопались в своих компах, ... покопались, и послали меня по маршруту Сан-Франциско, Лондон, СПб (первый перелет -- United, второй -- BA). Получилось, что я прилетел домой уже в 16:10. Это чуть позже, чем я рассчитывал оригинально, но зато перелет был всего с одной пересадкой (вместо Вашингтона и Франкфурта) и даже успевал на TCO Round 3 без напряга.

А раунд я слил. И дело даже не в усталости, а в том, что все мои знания по спортивному программированию я получил еще в школе и с тех пор мало освоил чего-либо нового в этой области. Век живи -- век учись. Собственно, я никогда в жизни не писал алгоритм нахождения минимального вершинного покрытия в двудольном графе, хотя знаю что его размер равен размеру максимального паросочетания (которое я умею искать). Примерно это и требовалось в 3-ей задаче. Так вот, написав за 15 минут до конца поиск паросочетания, я уже был не в состоянии придумать, как надо искать покрытие, хотя этот код пишется менее чем за 5 минут. Теперь буду знать.

Мораль проста -- можно прочитать 1000 книжек, но ты умеешь что-то программировать только тогда, когда ты это хотя бы раз в жизни запрограммировал лично. И это относится не только к спортивному программированию.

  • 1
Тут на мой взгляд немножко другая ситуация. А именно, для нахождения лексикографически первого вершинного покрытия совсем не нужно уметь строить его по паросочетанию. Моё решение (http://www.topcoder.com/stat?c=problem_solution&rm=264509&rd=10751&pm=7335&cr=10574855) работало так: в нём есть функция (evaluate), которая вычисляет мощность максимального паросочетания. Далее я пытаюсь по очереди все вершины с первой по последнюю добавлять в вершинное покрытие, и если при добавлении очередной вершины (и выкидывании смежных рёбер) мощность паросочетания в остатке уменьшается, то я её оставляю в покрытии, иначе возвращаю обратно.

Я делал то же самое. А что, можно по-другому?

Ага. Кстати, как найти какое-нибудь покрытие я таки придумал и написал минут за 5 до конца. Если я не ошибаюсь, то надо просто попытаться найти чередующуяся цепочку обходом в ширину и посмотреть до каких вершин оно доберется. Фактически находим минимальный разрез. Потом выбрать вершины из паросочетания находящиеся на границе разреза. Но, как ты правильно заметил, это совсем не то что требовалось в задаче -- я только зря потратил время.

Уже после конца соревнования я изучил твое решение -- элегантно, просто, и легко доказывается. Меньше чем за 5 минут я доделал то что у меня уже было написано до правильного решения.

(Deleted comment)
Так посмотрите решения этой задачи в архиве topcoder. progammer в комментарии выше послал ссылку на свое решение, в котором эта задача решается весьма элегантно.

Да и вообще, если вам просто вершинное покрытие, то это немного другая задача. Тут обсуждалась задача нахождения оного исключительно в двудольном графе. В общем случае это NP-полная задача, см. http://en.wikipedia.org/wiki/Vertex_cover_problem.



  • 1
?

Log in

No account? Create an account