Время: 10 дней (1 февраля — 10 февраля 2011 г.)
Конкурс завершён.
Посмотреть итоги.

В честь дня рождения моего блога предлагаю принять участие в очередном любительском конкурсе для программистов-математиков. Я обещал в прошлый раз, что конкурс будет по параллельным вычислениям, однако по техническим причинам его придётся пока отложить на неопределённый срок. Вместо этого будет простой конкурс с простой (с точки зрения теории сложности) задачей.

Год назад предлагалось перемножать матрицы на скорость. Это достаточно понятная задача, полезность которой в прикладной математике ни у кого не вызывает сомнения. Пусть это будет традицией – делать в феврале конкурс по линейной алгебре. Я предлагаю решать целочисленную систему линейных уравнений. На скорость. Сам я участия в конкурсе не принимаю. На этот раз никаких призов не будет, предлагаю участвовать исключительно ради интереса и при наличии свободного времени.

Продолжительность конкурса объявлена 10 дней (условно). Если этого времени не хватит, можем добавить.

Задача

Условие

Задана система линейных уравнений с целыми числами Ax=b. Матрица А имеет размер n×n и состоит из целых чисел. Вектор в правой части также целочисленный. Все числа умещаются в 32 бита со знаком (от −231 до 231−1). Очевидно, что решением этой системы будет вектор x, состоящий из рациональных чисел. Вот этот вектор и нужно отыскать. Разумеется, что числитель и знаменатель полученных дробей могут оказаться очень длинными, поэтому никто не запрещает использовать GMP или MPIR. Гарантируется, что заданная система имеет единственное решение.

Требования к программе

Требуется написать программу, которая считывает из файла «file.in» входные данные, и выводит в файл «file.out» ответ в виде вектора рациональных чисел. Формат входных и выходных данных указан ниже в примере.

Предлагается два варианта проверки решения участников.
(1) В почтовый ящик конкурса (см. ниже) присылается работающий EXE файл, который будет автоматически прогоняться по всем имеющимся тестам.
(2) Присылается программа, написанная на C/C++ (возможно с использованием библиотеки MPIR) которая будет откомпилирована на компьютере Core 2 Duo 8400 компилятором Intel C++ 11.1 c теми ключами компиляции, которые захочет участник (либо /O3, выбираемый мной по умолчанию). В этом случае программа должна быть написана в ОДНОМ файле с расширением CPP и использовать только библиотеку MPIR (или вообще без неё), и никаких других. Заголовочный файл MPIR подключается как обычно #include <mpir.h> после всех остальных заголовочных файлов. На уровне целых и рациональных чисел MPIR полность совместим с GMP, поэтому если у вас есть только GMP, то исправление gmp.h на mpir.h должно сработать.

Пример и пояснения к формату ввода / вывода

Во входном файле «file.in» в первой строке задается число n — размерность системы. В остальных n строках записано n+1 число. Первые n чисел в такой строке – элементы соответствующей строки матрицы, а последнее число – соответствующий элемент в правой части. Например, так может выглядеть входной файл

file.in
—————-
2
1 2 2
3 4 7
—————-
Это означает, что система имеет размерность 2, а уравнения системы имеют вид
x1+ 2x2=2,
3x1+ 4x2=7.

Ответ выводится в файл «file.out» по одному рациональному числу в строке. В данном случае x1=3 и x2=−1/2, поэтому содержимое файла должно быть таким:

file.out
—————-
3
−1/2
—————-
Обратите внимание на то, что если знаменатель рационального числа равен 1, то он не пишется. Программа проверяется автоматической системой, поэтому формат ввода / вывода должен строго соблюдаться. Дробь должна быть несократимой, числитель целым, а знаменатель натуральным.

Вы можете скачать пример системы для n=100 с ответом.

Положения

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

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

  1. Операционная система, на которой будет проходить тестирование — Windows 7 — 32 бита.
  2. Тестирование производится на компьютере с процессором Intel Core 2 Duo 8400 (3000 MHz) 4GB DDR2-800.
  3. Программа должна использовать не более одного процесса и одного потока в нём. Несмотря на то, что процессор двухъядерный, разрешается использовать только одно ядро на 100% его мощности.
  4. Запрещено использовать динамически-подключаемые библиотеки (dll).
  5. Программа может быть представлена в двух вариантах, указанных в требованиях к программе выше. Я отдаю себе отчёт в том, что усложняю возможность участия для тех, кто не может компилировать под Windows и не пишет на C/C++. Но других вариантов у меня нет и не предвидится.
  6. Программа должна использовать не более 2Gib (231 байт) оперативной памяти. Таково ограничение 32-битной ОС.
  7. Время работы программы на каждом тесте не должно превышать 600 секунд. Почему? Примерно столько работает написанный «в лоб» метод Гаусса в целых числах. Предполагается, что программы участников будут значительно быстрее.
  8. Максимальный порядок матрицы в тесте n = 200. Внимание: это ограничение может увеличиться, если кто-либо из участников напишет слишком быструю программу.
  9. Элементы матрицы и вектора правой части — целые числа, умещающиеся в 32 бита со знаком.
  10. Тестовые задания для программы почти полностью случайны. Никаких специальных тестов, которые давали бы максимально большие по объёму ответы не придумывалось.
  11. Программа должна работать в консольном режиме, то есть никаких графических интерфейсов писать не нужно. Ваша программа считывает данные из входного файла (который будет находится в той же директории), решает систему и выводит ответ в другой файл (в ту же директорию).
  12. Конкурс завершается 10 февраля ровно в 21 ч. 00 м. Пост с подведением итогов будет написан в течение суток.
  13. Я НЕ принимаю участия в конкурсе и НЕ вмешиваюсь в рассуждения участников и их решения от начала конкурса и до его завершения. Никому ничего не советую и не помогаю найти / понять / написать / скачать и т. д. Буду ограничиваться лишь общими комментариями по мере необходимости.
  14. Я оставляю за собой право менять правила проведения конкурса, если в них обнаружатся неточности.

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

  1. Во время проведения конкурса участники посылают на электронный адрес «zealint.comp@gmail.com» письмо с темой «Система линейных уравнений — Конкурс». В теме необходимо указать свой ник. Прикрепите к письму исполняемый файл или CPP файл с указанием желаемых ключей компиляции. Внимание: gmail не пропускает EXE файлы даже в сжатом виде, поэтому нужно переименовать их, например, в MP3.
  2. По мере тестирования поступающих программ, результат их работы будет указываться в таблице рейтинга, внизу этой страницы. Старайтесь не прысылать новые версии программ слишком часто — это будет создавать длинные очереди. Если участник посылает более одной версии за то время, пока почта не проверялась, учитывается только последняя версия, а остальные удаляются. Почта проверяется 4-5 раз в сутки.
  3. Присланная участником версия программы засчитывается и попадает в рейтинг только в том случае, если она выполняет все тесты без ошибок, укладывается в указанные ограничения по времени и по памяти, а также (если это не первая версия автора) работает быстрее его предыдущей программы.
  4. Победившим считается тот участник, программа которого оказалась самой быстрой на момент завершения конкурса.

Пожелания

Прочтите FAQ.

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

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

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

Недоброжелателей, троллей, и пр. прошу себя никак не проявлять.

Текущий рейтинг

Конкурс завершён.

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

  1. Shamil :: 10.02.11 :: C# :: 139,75 с.
  2. Dmitry :: 04.02.11 :: C++/msvс2008 :: 174,88 с.
  3. Velifaro :: 02.02.11 :: C++/msvс2008 :: 185,61 с.

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

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

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

Хабрахабр.

Клуб ПРОграммистов — Форум программистов.

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