Конкурс Программистов №2

Проект ttools.ru объявляет конкурс для программистов №2! О конкурсах проектов вы можете прочитать в разделе « Соревнования » блог ttools.ru Опыт предыдущего конкурса был учтен и отражен в правилах и плане конкурса.

О конкурсном задании №2: Задача будет сложнее и интереснее задачи конкурс №1 .

Однако по опыту первых соревнований я уверен, что сильнейшие участники смогут запрограммировать решение «в лоб» уже в течение первого часа.

Однако объем и характер данных для обработки выбраны таким образом, что при таком решении время вычислений будет значительным, что автоматически даст преимущество участникам с более оптимальным алгоритмом решения.

При этом оптимизация алгоритма не должна быть настолько сложной, чтобы время на ее реализацию было неоправданным и не давало преимущества другим участникам.

Вам нужно будет найти наиболее эффективное решение в кратчайшие сроки.

Надеюсь, вам понравится этот вызов! План соревнований:

  1. 14 марта 2011 года в 14.00 по московскому времени текст задачи будет опубликован на сайте ttools.ru.
  2. Исходными данными для задачи является файл, прикрепленный к тексту задачи.

    Для второго конкурса файл будет бинарным.

    Размер файла 12 000 000 байт, размер zip-архива 9 405 759 байт. Скачать файл заранее можно здесь: конкурс2 .

    На всякий случай можно проверить корректность загрузки контрольной суммой: MD5 (konkurs2_task.zip) = 331d04e0de3eb4f3aa69906a014d427d (хеш рассчитан плагин для далекого )

  3. Задачу можно решить на любом удобном языке программирования.

  4. Результатом решения задачи является файл, содержимое которого явно представляет собой правильный или неправильный ответ. Есть только один правильный ответ. Исходный код алгоритма решения от участника не требуется.

  5. Конкурс считается завершенным после объявления о завершении конкурса, после чего отзывы не принимаются.

    Об окончании конкурса будет объявлено, если в ходе обработки ответов будет получен хотя бы один правильный ответ, либо при отсутствии правильных ответов конкурс будет остановлен через неделю.

    Ответы будут обрабатываться один раз в сутки.

    Итоги конкурса (список участников, приславших правильное решение) и победитель будут объявлены в течение суток с момента окончания конкурса.

  6. На этот раз был учтен опыт предыдущего конкурса, поэтому денежного приза победителю этого конкурса не предусмотрено.

    Идея денежного приза вызвала негативные отзывы и подозрения в сговоре победителя и организатора.

    Несмотря на это, от участников были получены положительные отзывы о том, что идея проведения соревнований им понравилась, и что основной мотивацией является соревнование в решении интересных задач, а не денежный приз.

    Благодаря этим людям соревнования продолжатся.

    Мне хотелось бы сохранить именно эту атмосферу мотивации к участию в соревнованиях и именно такой клуб участников.

    Если вы не заинтересованы в решении задач без денежного приза, пожалуйста, не участвуйте.

  7. Поскольку в ходе предыдущего конкурса за максимальное количество решенных конкурсных задач была обещана денежная премия в размере 5000 рублей, обещание остается в силе.

    Результат будет рассчитан по итогам 10 соревнований.

    Я не буду никак доказывать справедливость распределения призов, кроме этого слова.

    Приз оставили только потому, что он был обещан ранее.

    Легче предположить, что его не существует. Если вам не нравятся данные условия участия, пожалуйста, не участвуйте.

    Однако, если вы участвовали в первом конкурсе, имеет смысл использовать один и тот же адрес электронной почты для второго и всех последующих конкурсов.

Правила конкурса:
  1. Принять участие в конкурсе может любой желающий.

  2. Специальной регистрации для участия в конкурсе не требуется.

    Подтверждением участия в конкурсе является вариант ответа во вложении к письму на адрес электронной почты [email protected]. Важный: Отправьте файл ответов не в архиве; имя файла должно совпадать с вашим адресом электронной почты и иметь расширение .

    dat. Те.

    если ваш адрес электронной почты «[email protected]», то файл в приложении должен называться «[email protected]».

    Ответы будут обрабатываться автоматически, остальные письма на этот адрес будут игнорироваться.

  3. У каждого участника есть только одна попытка.

    После отправки файла решения вы не сможете вносить изменения в свой ответ. Если участник получит 2 и более разных вариантов ответа, ни один не засчитывается.

  4. Победителем конкурса признается тот участник, который первым предложит правильное решение.

Текст задания и все необходимые исходные данные для второго конкурса.

будет опубликовано на сайте ttools.ru в понедельник, 14 марта 2011 года, в 14.00 по московскому времени.

Теги: #программирование #соревнования #Чулан


Доступный пространство объектов .

Каждый объект идентифицируется 4-байтовым идентификатором.

Между объектами есть направленные связи .

Каждая ссылка характеризуется идентификатором начального объекта, идентификатором объекта назначения и 4 байтами полезной нагрузки.

Последовательности соединений объект1-> объект2; объект2-> объект3;.

форма маршруты .

Длина маршрута определяется количеством подключений.

Через один объект может проходить несколько маршрутов.

Маршрут может быть закрыто , если конечный объект одной из ссылок маршрута является начальным объектом другой ссылки маршрута.

Длина закрытого маршрута — это количество ссылок до ссылки, в которой конечный объект является начальным объектом другой ссылки в маршруте, не включая эту ссылку.

Входной файл содержит список соединений в формате: 4 байта исходный идентификатор объекта 4 байта идентификатор целевого объекта 4 байта информационная нагрузка связи Необходимый Найдите во входном файле маршрут (маршруты, если их несколько) максимальной длины и сохраните его в выходном файле в формате 4 байта длина маршрута 12 x длина маршрута список ссылок на маршруты Напомню, что правила конкурса, а также исходный файл можно найти Здесь Удачи !!!

УПД:

В настоящее время (15.03.2011 17:30)

есть 2 ответа,

анализ 1-го ответа:

является ли файл файлом маршрутов: нет

анализ 2-го ответа:

является ли файл файлом маршрутов: да

количество маршрутных стыковок: 264

маршрут открыт: да

это маршрут вариант ответа: да

но длина маршрута не максимальная, в файле есть еще маршруты, не все так просто.

Пока правильных ответов нет, конкурс продолжается.

УПД: В настоящее время (16.03.2011 17:00) нет новых ответов Учитывая динамику соревнований, правило одной попытки отменено.

УПД: В настоящее время (17.03.2011 18:00) нет новых ответов конкурс продолжается Итак, неделя закончилась с момента анонса конкурс программистов №2 В ходе конкурса было предложено 2 ответа, 0 правильных ответов.

Проблема оказалась неразрешимой и будет законсервирована на неопределенный срок.

Дорогой читатель! Если вы читаете этот пост спустя 300 лет после его публикации (может быть, чуть раньше или чуть позже), знайте, что в 2011 году эта задача считалась сложной, и я не знаю никого (кроме себя), кто мог бы решить ее в менее одной недели.

Тактовая частота процессора среднего компьютера в наше время составляла 3 ГГц, а среднее количество процессоров на одном компьютере — четыре.

Если вам удастся решить задачу, пожалуйста, дайте мне знать, и если я еще жив, я напишу на страницах своего блога, какой вы крутой ;) УПД: Задача конкурс №2 для программистов решено в этом тысячелетии! Результат анализа файла: является ли файл маршрутом: да количество маршрутных соединений: 90899 маршрут открыт: да это маршрут вариант ответа: да Ответ был получен 31 марта, через 17 дней после объявления конкурса.

Имя героя Алексей! [ эскоман@ ] Поздравляем! Похоже, не так много людей могут решить эту проблему, и это действительно здорово!

Мини-интервью: :) Чтобы упростить решение задачи №2, я сразу отсортировал исходный файл по полю FromPoint и сохранил его.

Это помогло позже использовать бинарный поиск по списку соединений.

Плюс к исходным полям подключения (FromPoint, ToPoint и Data) я добавил поле MaxLen — поле, в котором хранится максимальное количество соединений, проходящих через это соединение.

Кроме того, это поле является индикатором того, прошел ли алгоритм через соединение или нет. Это позволило нам избежать использования одних и тех же соединений несколько раз.

В результате полученному алгоритму поиск решения на моем ноутбуке занимает около 2 часов.

Хотя есть узкие места, которые можно исправить.

Теги: #программирование #соревнования #Чулан
Вместе с данным постом часто просматривают: