Имеется пространство объектов. Каждый объект идентифицируется 4-х байтовым идентификатором. Между объектами имеются направленные связи. Каждая связь характеризуется идентификатором начального объекта, идентификатором конечного объекта и 4 байтами информационной нагрузки. Последовательности связей объект1->объект2; объект2->объект3;… образуют маршруты. Длина маршрута определяется количеством связей. Через один объект может проходить несколько маршрутов. Маршрут может быть замкнутым, если конечный объект одной из связей маршрута является начальным объектом другой связи маршрута. Длиной замкнутого маршрута считается количество связей до связи, в которой конечный объект является начальным объектом другой связи маршрута, не включая данную связь.
Входной файл содержит список связей в формате:
4 байта идентификатор начального объекта
4 байта идентификатор конечного объекта
4 байта информационная нагрузка связи
Необходимо
Найти маршрут (маршруты, если их несколько) максимальной длины во входном файле и сохранить в выходном файле в формате
4 байта длина маршрута
12 x длина маршрута список связей маршрута
Напоминаю, правила проведения конкурса, а также исходный файл можно найти здесь
Удачи !!!
UPD:
На текущий момент (15.03.2011 17:30)
имеется 2 ответа,
анализ 1-го ответа:
является ли файл файлом маршрутов: нет
анализ 2-го ответа:
является ли файл файлом маршрутов: да
количество связей маршрута: 264
является ли маршрут незамкнутым: да
является ли маршрут вариантом ответа: да
но длина маршрута не максимальна, в файле есть маршруты больше, не всё так просто.
Пока верных ответов нет, конкурс продолжается
UPD:
На текущий момент (16.03.2011 17:00)
новых ответов нет
учитывая динамику конкурса правило одной попытки отменено
UPD:
На текущий момент (17.03.2011 18:00)
новых ответов нет
конкурс продолжается
Итак, закончилась неделя с момента объявления конкурса для программистов №2
За время проведения конкурса было предложено 2 ответа, правильных ответов — 0. Задача оказалась нерешаемой и будет законсервирована на неопределенный срок.
Уважаемый читатель! Если ты читаешь эту запись через 300 лет после ее опубликования (может чуть раньше или чуть позже) знай, что в 2011 году эта задача считалась сложной, и я не знаю никого (кроме себя), кто смог бы ее решить менее, чем за одну неделю. Тактовая частота процессора среднего компьютера в наше время составляла 3 Ггц, среднее количество процессоров одного компьютера равнялось четырем. Если получится решить задачу, сообщи пожалуйста мне, и, если я буду еще жив, напишу на страницах своего блога, насколько ты крут ;)
UPD:
Задача конкурса №2 для программистов решена в этом тысячелетии!
Результат анализа файла:
является ли файл маршрутом: да
количество связей маршрута: 90899
является ли маршрут незамкнутым: да
является ли маршрут вариантом ответа: да
Ответ был получен 31 марта, спустя 17 дней после объявления конкурса.
Имя героя — Алексей! [ escoman@ ]
Поздравляю! Похоже, людей способных решить эту задачу не очень много, это действительно круто!
Входной файл содержит список связей в формате:
4 байта идентификатор начального объекта
4 байта идентификатор конечного объекта
4 байта информационная нагрузка связи
Необходимо
Найти маршрут (маршруты, если их несколько) максимальной длины во входном файле и сохранить в выходном файле в формате
4 байта длина маршрута
12 x длина маршрута список связей маршрута
Напоминаю, правила проведения конкурса, а также исходный файл можно найти здесь
Удачи !!!
UPD:
На текущий момент (15.03.2011 17:30)
имеется 2 ответа,
анализ 1-го ответа:
является ли файл файлом маршрутов: нет
анализ 2-го ответа:
является ли файл файлом маршрутов: да
количество связей маршрута: 264
является ли маршрут незамкнутым: да
является ли маршрут вариантом ответа: да
но длина маршрута не максимальна, в файле есть маршруты больше, не всё так просто.
Пока верных ответов нет, конкурс продолжается
UPD:
На текущий момент (16.03.2011 17:00)
новых ответов нет
учитывая динамику конкурса правило одной попытки отменено
UPD:
На текущий момент (17.03.2011 18:00)
новых ответов нет
конкурс продолжается
Итак, закончилась неделя с момента объявления конкурса для программистов №2
За время проведения конкурса было предложено 2 ответа, правильных ответов — 0. Задача оказалась нерешаемой и будет законсервирована на неопределенный срок.
Уважаемый читатель! Если ты читаешь эту запись через 300 лет после ее опубликования (может чуть раньше или чуть позже) знай, что в 2011 году эта задача считалась сложной, и я не знаю никого (кроме себя), кто смог бы ее решить менее, чем за одну неделю. Тактовая частота процессора среднего компьютера в наше время составляла 3 Ггц, среднее количество процессоров одного компьютера равнялось четырем. Если получится решить задачу, сообщи пожалуйста мне, и, если я буду еще жив, напишу на страницах своего блога, насколько ты крут ;)
UPD:
Задача конкурса №2 для программистов решена в этом тысячелетии!
Результат анализа файла:
является ли файл маршрутом: да
количество связей маршрута: 90899
является ли маршрут незамкнутым: да
является ли маршрут вариантом ответа: да
Ответ был получен 31 марта, спустя 17 дней после объявления конкурса.
Имя героя — Алексей! [ escoman@ ]
Поздравляю! Похоже, людей способных решить эту задачу не очень много, это действительно круто!
Мини-интервью: :)
Для упрощение решения задания №2 я сразу отсортировал исходный файл по полю FromPoint и сохранил его. Это помогло в последствии использовать бинарный поиск по списку связей.
Плюс к исходным полям связи (FromPoint, ToPoint и Data) я добавил поле MaxLen — поле, хранящее максимально количество связей, проходящих через данную связь. Кроме того, данное поле является индикатором — проходил ли алгоритм через связь или нет. Это позволило не ходить по одним и тем же связям по несколько раз.
В итоге полученный алгоритм на моём ноутбуке ищет решение около 2-х часов. Хотя есть узкие места, которые можно улучшить...
