Конкурс на решение целочисленной системы линейных уравнений

[@hellman]

Отлично! А когда окончание конкурса?

[@Zealint]

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

[@AlDev]

>>Windows 7 (32 бита), поэтому можно либо присылать EXE файлы, либо CPP исходники, которые будут компилироваться на рабочей машине (в этом случае доступна только библиотека MPIR).

Печаль

[@Zealint]

Сожалею, но я сильно ограничен в возможностях.

[@AlDev]

Ладно, заюзаем виртуалки :)
Задача интересная, спасибо

[@icc]

А один тест для отладки в открытый доступ не выложите?

[@Zealint]

Такого не предполагается. Считается, что участник в состоянии сам придумать небольшой тест. А большой тест можно сгенерировать в любой системе компьютерной алгебры типа Maple. Но как вы его будете отлаживать, я не знаю.

[@tangro]

Да Вы что — серьезно предлагаете делать что-то без примера входных и выходных данных? Да на самых забитых сельских школьных олимпиадах по информатике тесты даются в 100%-ах случаев.

[@Zealint]

Ручной пример (n=2) приведён на странице конкурса, пример для n=100 добавил туда же.

[@AlDev]

Эм. Методом Гаусса сделать тест-проверялку не айс?

[@Zealint]

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

[@lorc]

А в каком формате принимать данные и возвращать результат? Если каждый будет делать по своему — тяжело будет делать автоматические тесты

[@hx0]

zealint.ru/integer-linear-system-comp.html

Тут есть примеры. И по поводу теста для отладки тоже.

[@ariel32]

А как будет определятся быстродействие программ?

[@Zealint]

Это делается с помощью специальной системы тестировани, которая испльзуется для проведения олимпиад. Она измеряет процессорное время с точностью около 1/10 секунды (иногда хуже, если кино смотреть). Аналогичная система использовалась здесь.

[@fllln]

А что выводить в случае, если ранг матрицы А меньше n, и соответственно решений более одного? Или в ваших тестах решение всегда единственное?

[@Zealint]

В условиях написано:
«Гарантируется, что заданная система имеет единственное решение».

[@fllln]

Ох, и правда. Извиняюсь, проглядел.

[@Bobylov]

А какой толк вообще решать систему одинарной точности с 200 неизвестных, если решение даже системы с тысячей неизвестных двойной точности методом сопряженных градиентов занимает время, сравнимое с погрешностью вычисления микросекунд?

[@Zealint]

Не понял вас. Вы можете представить программу, которая точно решает поставленную задачу «за время, сравнимое с погрешностью вычисления микросекунд»?

[@hellman]

нужно без погрешностей, дроби в ответе

[@CAH4A]

Ну это смотря какая обусловленность матрицы.

[@jerom]

Сделал Гаусса в один поток, но тоже на perl.

На этом тестовом файле из 100 работает около 30 секунд.

На реально случайной матрице 200×200 (а не почти нулевой, как эта) – 18 минут (на машине автора будет минут 12-14).

[@Zealint]

Ну а нельзя слегка ускорить? Из Perl вроде бы можно сделать EXE. Если хотите, присылайте, скажу точную скорость.

[@jerom]

В один поток особо не ускорить, в 2 потока минут 8 будет.

Но со сборкой win-exe под linux проблем больше, чем с написанием кода :)