Конкурс на самое быстрое решение задачи о назначениях завершён. Подведём итоги.

Окончательный рейтинг

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

  1. halyavin :: Linux-64 :: g++ :: 1,03 с.
  2. alexBlack :: Win-32 :: Delphi :: 5,35 с.
  3. ArtemKim :: Win-32 :: C MSVC2010 :: 7,64 с.
  4. Silent :: Win-32 :: C++ VS2008 :: 19,75 с.

Поздравляем победителя!

Архив конкурса

Все желающие могут скачать архив конкурса. В нём содержится простая тестирующая система, взятая с олимпиад по программированию; она древняя, но работает. Там же лежит генератор тестов (всегда одинаковых) и правильных ответов к ним вместе с программами всех участников или их исходными кодами (кто что присылал), моя лучшая программа (2 с. под Win32 и 1,2 с. под Linux64) тоже там есть. Программа победителя называется «ScalePushRelabel.cpp» (чтобы скомпилировать её под Win32 я покопался в коде и переписал несколько строк, поэтому exe файл я потом удалил и даю исходник как есть без изменений, компилируйте лучше под Linux — там под g++ работает без изменений). В конце конкурса halyavin заметил, что среди тестов нет такого, в котором матрица состоит из нулей. Мой косяк. Я удалил три последних теста и добавил вместо них нулевые, к счастью, на результаты конкурса это не повлияло.

Скачать архив (700 Кб).

Поясню, как этим пользоваться. Для начала нужно зайти в папку tchoose/tests и сгенерировать тесты программой gen.exe (исходник этой программы там же). После этого нужно запустить solve.bat — этот скрипт решает все тесты с помощью моей программы solution.exe (это моя медленная версия – 18 с., — но гарантированно правильная), и сохраняет ответы. После этого в директории появятся файлы 01, 01.a, 02, 02.a и т. д. Будьте внимательны, все тесты с решениями занимают 1 Гб, убедитесь, что на вашем диске хватает места.

После того, как тесты сгенерированы, зайдите в папку tchoose/solutions и положите туда свою программу (программы авторов с исходниками хранятся там же). Теперь запустите tchoose.exe из папки tchoose и следуйте интуитивно понятному интерфейсу (нажмите внизу кнопку проверки решений). Если возникнут проблемы, нужно прочитать readme.txt, в котором также написано, как можно изменить входные и выходные файлы, ограничения по времени и по памяти.

Можете запустить все программы на всех тестах и убедиться в том, что окончательная таблица рейтинга составлена правильно (кроме решения победителя, которое нужно тестировать в Linux64). Конечно, времена работы у Вас могут отличаться.

В директории tchoose есть файл check.cpp — это чекер, написанный по правилам этой системы. Работает на основе кода из testlib.h (этот файл есть в архиве). Чекер простой: читает ответ участника, сверяет численно значение с эталоном и проверят, что выведенное назначение является правильным и даёт ту же сумму, что получена программой.

Любителей Linux прошу меня простить, аналогичной программы для Linux я не знаю. Для этого случая я просто на коленках собрал shell-скрипт из 5-6 строк, который прогоняет программу по тестам и также сверяет ответы с помощью чекера, но вместо измерения времени смотрит, что вывела программа в поток ошибок. Это вы сможете сами написать, если нужно.

Моё решение (кратко)

У меня несколько решений, время работы которых разное: от 3,5 секунд до нескольких минут. Но когда конкурс начался и я стал получать замечания о качестве проведения соревнования (по поводу больших файлов и долгого ввода), я возразил, что это не важно, и чтобы не быть голословным, быстро переписал ввод через scanf, заменив его отображением файла в память с ручным парсингом чисел. Лучшая версия стала работать 2 секунды, вместе с вводом данных, который теперь стал занимать меньше 1/3 с.

Можно решать задачу венгерским методом, самая короткая программа для которого (из известных мне) уже прозвучала на форуме (вот ссылка на неё), только в такой реализации предложенная программа выглядит неприлично. Нужно как минимум убирать оттуда STL и разные извращения, возникшие из-за того, что отсчёт элементов там идёт от нулевого. Когда речь идёт об удобстве и скорости кодирования, всё замечательно, но если нужна скорость программы, лучше использовать обычные массивы и матрицы. Участник alexBlack как раз присылал эту версию на форуме, она работала 53 секунды. В моём исполнении она работала 18 секунд, а если добавить разных эвристик (например, сначала найти максимальное паросочетание в приведённой матрице, а потом его улучшать), то можно даже сделать 5-7 секунд на предложенных тестах. Однако все такие эвристики всё равно можно завалить.

Моя худшая версия использовала прямолинейное сведение задачи о назначениях к задаче о поиске потока минимальной стоимости. Алгоритмы Successive Shortest Path или Cost Scaling в этом случае работали ну очень долго.

Разумеется, что в таких случаях нужно учитывать и то, что граф является двудольным, и то, что пропускные способности рёбер равны единице. Так вот, самое лучшее, что мне удалось найти – алгоритм Cost Scaling с двойным проталкиванием предпотока, специально модифицированный под задачу о назначениях: он работал на моих тестах 2 секунды (после ускорения ввода). Методов, реализующих этот подход, несколько. Я не помню, где изучал данные методы, но специально для конкурса нашел эту ссылку, где на с. 28-29 есть описание одного из них. Только чтобы его понять, нужно начать читать гораздо раньше, и знать в общих чертах теорию потоков.

Моё изменение в этом алгоритме состоит в том, что вместо проталкивания предпотока из активных вершин в произвольном порядке, я выполняю проталкивание по очереди из всех вершин, которые начинают образовывать коллизии после проталкивания. Так программа получается быстрее (я не знаю, почему) и проще. Исходник этой программы вы найдёте в архиве и убедитесь, что её основная часть значительно короче реализации венгерского метода. Ещё одно улучшение, связанное с пересчётом потенциалов я подсмотрел в коде победителя конкурса. Программу это не ускорило, но она стала немного короче.

Интересно то, что победитель конкурса использовал этот же метод, только немного иначе написанный. Вообще-то я не ожидал, что в Linux-64 будет настолько быстрее, и свою программу до начала конкурса там не тестировал. Если бы догадался протестировать, наверное наступил бы себе на горло и забацал бы тесты побольше. Но всё обошлось.

Пояснения к конкурсу

Почему такие ограничения? С одной стороны, не хотелось давать слишком больших ограничений по n, иначе тесты были бы слишком хилыми. Дело в том, что для венгерского метода худшими были тесты типа Cij = i*j или Cij = i+j, особенно если после получения такой матрицы, случайно перетасовать столбцы и строки. Тест 72 как раз содержал такую матрицу суммы и на нём хуже всего работали вариации на тему венгерского метода. Остальные алгоритмы хуже всего работали на таблице умножения, но её, к сожаления при n=2000 не было, так как иначе это нарушало бы ограничение на максимальный элемент в матрице. Вместо этого таблица умножения бралась по модулю максимального ограничения по C. Тест 39, на котором тормозили многие программы, как раз из этой серии.

Тесты большего размера потребовали бы использование int64, почему-то мне этого не хотелось. С другой стороны, метод Cost Scaling в любом случае работает только с 64-битовыми числами, так как нужно либо использовать плавающую арифметику, либо умножать все элементы матрицы на n. Мне хотелось, чтобы методы, не требующие таких манипуляций, работали при ограничениях в 32 бита.

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

Смысл этого конкурса

Когда-то давно я занимался теорией потоков и набрал некоторое количество опыта в этой теме. Например, по ссылке на венгерский метод, что приведена выше, автор кода ссылается на псевдокод А. Лопатина из книги Оптимизация на графах (алгоритмы и реализация), один из авторов которой я.

Теперь я занимаюсь перечислительной комбинаторикой, но чтобы не хоронить свои наработки, решил устроить конкурс, чем побудить участников разобраться в задаче и получить новых знаний по теме, а потом поделиться тем, что сам знаю. Уверен, что пользу это кому принесло. По крайней мере, теперь больше людей знает об очень коротком и быстром решение задачи о назначения: в моей программе суммарное число строк, которые относятся именно к алгоритму, около 30, 16 из которых занимает программа поиска двух минимумов в массиве. Кстати, если кому-то потребуется ещё ускорить программу, то узким местом в ней является как раз процедура поиска первого и второго минимумов. Можно либо аппаратно её ускорять, либо приделать какую-нибудь хитрую структуру данных. В общем, кому надо дальше ускорять – пробуйте. Потом расскажете : )

Другим направлением дальнейшей работы может стать сочинение худших тестов для алгоритма Cost Scaling. Если кто-то придумает, на чём метод победителя конкурса работает очень медленно — пишите на форум, обсудим.

Всем огромное спасибо за участие!

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