Время: 2 недели (1 октября — 15 октября 2011 г.)
Конкурс завершён, смотрите итоги.

Таблица участников.

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

Постановка задачи

На самом деле, задача о назначениях в особом представлении не нуждается. Алгоритм её решения входит в репертуар почти любого участника соревнований по спортивному программированию. Можно отыскать в Интернете множество формулировок, приложений, и готовых (хороших и плохих, правильных и неправильных) решений. Я буду формулировать её следующим образом. Имеется квадратная матрица (Cij) порядка n, состоящая из целых чисел. Требуется выбрать в матрице n чисел так, чтобы в каждой строке и в каждом столбце было выбрано ровно одно число, и при этом сумма выбранных чисел была бы минимально возможной. Например, пусть n=3, и матрица имеет вид

1 2 3
3 6 9
2 4 6

Минимальной будет сумма 10, образуемая подчёркнутыми числами.

Ограничения

Поскольку мы не на олимпиаде, где часто требуется уложиться в 2 секунды, предлагаю ограничение 1≤n≤2000, а сами числа в матрице целые, ограниченные по модулю величиной 1073741.

Победит тот, чья программа будет работать максимально быстро. Но чтобы не было откровенно плохих решений, программа должна укладываться в 15 минут на любом отдельно взятом тесте. (По поводу тестирования см. ниже).

Ввод и вывод

Ваша программа должна считать исходные данные из файла input.txt. В нём в первой строке записано число n, а в последующих строках — сама матрица. Например,
— файл input.txt ————————————————
3
1 2 3
3 6 9
2 4 6
—————————————————————-

Ответом считается сама сумма, выведенная в файл output.txt в первой строке и назначение, на котором данная сумма достигается — во второй. Назначение — это последовательность ai номеров столбцов, соответствующих строкам i. То есть пары (i,ai) для i=1,2,…,n являются номерами выбранных элементов матрицы C. Для нашего примера имеем ответ
— файл output.txt ———————————————-
10
3 1 2
—————————————————————-

Это означает, что выбраны элементы (1,3), (2,1) и (3,2). Если ответов несколько, можно выводить любой.

Положения

Общие правила и ограничения

  1. Операционная система — Windows 7 — 32 бита. Или Linux Ubuntu 10.04 – 64 бита, но с ограничением (см. ниже)
  2. Тестирование производится на компьютере с процессором Intel Core 2 Duo 8400 (3000 MHz) 4GB DDR2-800.
  3. Программа должна использовать не более одного процесса и одного потока в нём. Несмотря на то, что процессор двухъядерный, разрешается использовать только одно ядро на 100% его мощности.
  4. Запрещено использовать динамически-подключаемые библиотеки (dll).
  5. Можно присылать решения в нескольких вариантах. Либо EXE файл для Windows (и он должен работать корректно без необходимости установки дополнительного ПО). Либо CPP файл, который я буду компилировать с помощью Intel C++ 11 под Win или gcc под Linux (но в этом случае я не гарантирую, что он будет компилироваться, если вы используете какие-то нестандартные библиотеки). Либо исполняемый файл под Linux Ubuntu 10.04 – 64 бита. ВНИМАНИЕ. В случае работы на Linux вам придется добавить в программу свой таймер, который в конце работы должен вывести время работы (секунды + сотые) в поток ошибок. К сожалению, замерять правильно время работы в Linux я иначе не умею.
  6. Программа должна использовать не более 1Gib (230 байт) оперативной памяти.
  7. Время работы программы на каждом тесте не должно превышать 900 секунд.
  8. Программа должна работать в консольном режиме, то есть никаких графических интерфейсов писать не нужно. Ваша программа считывает матрицу из входного файла (который будет находится в той же директории), что-то считает и выводит ответ в другой файл (в ту же директорию).
  9. Конкурс завершается 15 октября ровно в 12 ч. 00 м.
  10. Я оставляю за собой право менять правила проведения конкурса, если в них обнаружатся неточности.

Порядок проведения конкурса

  1. Во время проведения конкурса участники посылают на электронный адрес «zealint.comp@gmail.com» письмо с темой «Задача о назначениях — Конкурс». В теме необходимо указать свой ник, язык программирования и название компилятора, которым вы пользовались. Прикрепите к письму файл, который будет тестироваться. Файл назовите «ваш-ник.mp3». Внимание: gmail не пропускает EXE файлы даже в сжатом виде. Давайте переименовывать их в mp3 или ещё как-то иначе.
  2. Почта проверяется случайно не менее 1 раза в сутки. Рейтинг обновляется сразу после тестирования решений. Решения на Linux будут проверяться дольше (руками), чем решения для Windows (автоматически).
  3. По мере тестирования поступающих программ, результат их работы будет указываться в таблице рейтинга, внизу этой страницы. Участник может присылать новые версии программы не более одного раза в сутки. Если участник посылает более одной версии за сутки, учитывается только последняя, а остальные удаляются.
  4. Присланная участником версия программы засчитывается и попадает в рейтинг только в том случае, если она выполняет все тесты без ошибок, укладывается в указанные ограничения по времени и по памяти.
  5. Для тестирования подготовлено 100 тестов, большая часть из которых — просто случайные матрицы разных размеров (от минимальной до максимальной). Но на них время работы не обязательно максимально. Вид худшего теста зависит от вашего алгоритма. Я попытался сочинить худших тестов на разные случаи, но не обещаю, что учёл всё.
  6. Победившим считается тот участник, программа которого оказалась самой быстрой на момент завершения конкурса.

Пожелания

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

Если пишите комментарии на форуме, то подписывайтесь тем ником, который у вас отображается в таблице рейтинга (если отображается).

Ознакомьтесь с FAQ по конкурсам (игнорируя денежные вопросы).

Таблица участников

Конкурс завершён, смотрите итоги.

Таблица ниже будет постоянно обновляться по мере поступления новых программ. Внимание: прежде чем присылать программу, убедитесь, пожалуйста, что она укладывается в отведённое время на самом большом тесте, который вы сможете придумать сами и при этом не использует оперативной памяти больше, чем указано в правилах. Удачи!

  1. halyavin[v1] :: 10.10.2011 :: Linux-64 :: g++ :: 1,03 с.
  2. alexBlack[v4] :: 12.10.2011 :: Win-32 :: Delphi :: 5,35 с.
  3. alexBlack[v3] :: 09.10.2011 :: Win-32 :: Delphi :: 7,36 с.
  4. ArtemKim[v2] :: 09.10.2011 :: Win-32 :: C MSVC2010 :: 7,64 с.
  5. ArtemKim[v1] :: 07.10.2011 :: Win-32 :: C MSVC2010 :: 8,42 с.
  6. alexBlack[v2] :: 08.10.2011 :: Win-32 :: Delphi :: 8,64 с.
  7. alexBlack[v1] :: 07.10.2011 :: Win-32 :: Delphi :: 14,96 с.
  8. Silent[v2] :: 07.10.2011 :: Win-32 :: C++ VS2008 :: 19,75 с.
  9. Silent[v1] :: 06.10.2011 :: Win-32 :: C++ VS2008 :: 21,78 с.

Следите за конкурсами на моём блоге.

Информационные спонсоры

dxdy.ru — Научный форум.

Обсуждение конкурса на форуме в этой теме.