[Logo] Форум DL
  [DL]  На главную страницу 
Индекс форума ->Олимпиадное программирование ->Обсуждение Sphere-задач
Автор Сообщение
Владимир Миняйлов

Темы: 9
Сообщений: 30

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

Темы: 1982
Сообщений: 47183

Мой профиль
Молодец Вова - краткость - сестра таланта.
Но мне кажется, было бы здорово ПРЯМО здесь либо прямую ссылку сделать на условие задачи (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"...
Михаил Долинский

Темы: 1982
Сообщений: 47183

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

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

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

Темы: 6
Сообщений: 37

Мой профиль
Условие я уже написал, а вот ваша ссылка не работает...


______________________
Nothing is impossible; impossible itself says: "I m possible"...
Владимир Миняйлов

Темы: 9
Сообщений: 30

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

Темы: 0
Сообщений: 4

Мой профиль
Эта задача решается средствами линейной алгебры:

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