Автор |
Сообщение |
03.09.2006 18:25:46
Тема: HIGH
|
Владимир Миняйлов
Темы: 9
Сообщений: 30
Мой профиль
|
Пробывал BFS и хэш, но TL...
Самые лучшие решения палят за 0.1...
Может есть какая-то формула под это дело?
|
04.09.2006 10:52:00
Тема: Re:HIGH
|
Михаил Долинский
Темы: 1982
Сообщений: 47183
Мой профиль
|
Молодец Вова - краткость - сестра таланта.
Но мне кажется, было бы здорово ПРЯМО здесь либо прямую ссылку сделать на условие задачи (HIGH - если я правильно понял краткого Вову) либо коротко по-русски сформулировать ЗДЕСЬ условие задачи.
А еще лучше сделать и то, и другое. Тогда бОльшее число людей могло бы подключиться к "мозговому штурму".
Гена Короткевич - а ты решил эту задачу?
|
04.09.2006 14:27:21
Тема: Re:HIGH
|
Геннадий Короткевич
Темы: 6
Сообщений: 37
Мой профиль
|
Нет, пока не решил.
Условие читал и раньше, даже думал, но идей про полное решение не было
А ссылка на условие задачи с названием, например, ABC, такая: www.spoj.pl/problems/ABC/.
Edit: что интересно, когда я вставил ссылку с http, двоеточие и слеш (": /") заменилось на смайлик
2Edit: Вкратце условие:
Есть неориентированный граф на 12 вершин. Нужно определить количество способов оставить в нем остов. Ответ влазит в 64-битное знаковое целое.
7 секунд, 1000 тестов (но далеко не все максимальные).
______________________
Nothing is impossible; impossible itself says: "I m possible"...
|
04.09.2006 14:36:30
Тема: Re:HIGH
|
Михаил Долинский
Темы: 1982
Сообщений: 47183
Мой профиль
|
Спасибо за посказку, Гена и за краткое русское условие.
А вот ссылка на английское условие .
Руслан, у меня не работали все три варианта ссылки, потом вдруг все три заработали - я удалил все кроме первого - он опять не стал работать - пришлось вернуть все обратно. Как оказалось - URL-ы не работают, если НЕ ОТКЛЮЧИТЬ смайлики - Руслан - это неочевидно ...
особенно если я применяю твой тег (BB-код?) [url]
Руслан: проблем со смайликами в ссылках теперь быть не должно. Лишние ссылки я удалил.
Гена - внизу есть опция - отключить смайлики ...
Теперь (при отключенных смайликах) все ссылки снова работают ...
|
04.09.2006 14:39:26
Тема: Re:HIGH
|
Геннадий Короткевич
Темы: 6
Сообщений: 37
Мой профиль
|
Условие я уже написал, а вот ваша ссылка не работает...
______________________
Nothing is impossible; impossible itself says: "I m possible"...
|
04.09.2006 17:37:34
Тема: Re:HIGH
|
Владимир Миняйлов
Темы: 9
Сообщений: 30
Мой профиль
|
Есть мысль. Я пытался использовать алгоритм на основе Краскала, но это медленно. А что если пытаться исползовать что-то на основе Прима? Как вариант битовая маска из вершин связных с 1. Но не ясно как учитывать повторы...
|
07.09.2006 12:57:48
Тема: Re:HIGH
|
Иван Метельский
Темы: 0
Сообщений: 4
Мой профиль
|
Эта задача решается средствами линейной алгебры:
http://www.intuit.ru/department/algorithms/graphsuse/11/4.html
|
|