[Logo] Форум DL
  [DL]  Back to home page 
Forum Index ->Олимпиадное программирование ->Обсуждение Sphere-задач
Author Message
Vladimir Minyaylov

Topics: 9
Messages: 30

My Profile
Пробывал BFS и хэш, но TL...
Самые лучшие решения палят за 0.1...
Может есть какая-то формула под это дело?
Mihail Dolinskiy

Topics: 1530
Messages: 36538

My Profile
Молодец Вова - краткость - сестра таланта.
Но мне кажется, было бы здорово ПРЯМО здесь либо прямую ссылку сделать на условие задачи (HIGH - если я правильно понял краткого Вову) либо коротко по-русски сформулировать ЗДЕСЬ условие задачи.
А еще лучше сделать и то, и другое. Тогда бОльшее число людей могло бы подключиться к "мозговому штурму".
Гена Короткевич - а ты решил эту задачу?
Gennadiy Korotkevich

Topics: 6
Messages: 37

My Profile
Нет, пока не решил.
Условие читал и раньше, даже думал, но идей про полное решение не было
А ссылка на условие задачи с названием, например, ABC, такая: www.spoj.pl/problems/ABC/.

Edit: что интересно, когда я вставил ссылку с http, двоеточие и слеш (": /") заменилось на смайлик

2Edit: Вкратце условие:
Есть неориентированный граф на 12 вершин. Нужно определить количество способов оставить в нем остов. Ответ влазит в 64-битное знаковое целое.
7 секунд, 1000 тестов (но далеко не все максимальные).


______________________
Nothing is impossible; impossible itself says: "I m possible"...
Mihail Dolinskiy

Topics: 1530
Messages: 36538

My Profile
Спасибо за посказку, Гена и за краткое русское условие.
А вот ссылка на английское условие .

Руслан, у меня не работали все три варианта ссылки, потом вдруг все три заработали - я удалил все кроме первого - он опять не стал работать - пришлось вернуть все обратно. Как оказалось - URL-ы не работают, если НЕ ОТКЛЮЧИТЬ смайлики - Руслан - это неочевидно ...
особенно если я применяю твой тег (BB-код?) [url]
Руслан: проблем со смайликами в ссылках теперь быть не должно. Лишние ссылки я удалил.

Гена - внизу есть опция - отключить смайлики ...
Теперь (при отключенных смайликах) все ссылки снова работают ...
Gennadiy Korotkevich

Topics: 6
Messages: 37

My Profile
Условие я уже написал, а вот ваша ссылка не работает...


______________________
Nothing is impossible; impossible itself says: "I m possible"...
Vladimir Minyaylov

Topics: 9
Messages: 30

My Profile
Есть мысль. Я пытался использовать алгоритм на основе Краскала, но это медленно. А что если пытаться исползовать что-то на основе Прима? Как вариант битовая маска из вершин связных с 1. Но не ясно как учитывать повторы...
Ivan MetelSkiy

Topics: 0
Messages: 4

My Profile
Эта задача решается средствами линейной алгебры:

http://www.intuit.ru/department/algorithms/graphsuse/11/4.html
 
Forum Index ->Олимпиадное программирование ->Обсуждение Sphere-задач
Time:0,047