Zealint Feb 1 2011 at 11:39

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

2 min

2.6K

Sport programming*

+33

Comments 25

hellman Feb 1 2011 at 12:26

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

Zealint Feb 1 2011 at 12:33

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

AlDev Feb 1 2011 at 12:41

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

Печаль

Zealint Feb 1 2011 at 12:45

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

AlDev Feb 1 2011 at 12:49

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

icc Feb 1 2011 at 12:42

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

Zealint Feb 1 2011 at 12:47

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

tangro Feb 1 2011 at 12:53

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

Zealint Feb 1 2011 at 13:01

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

AlDev Feb 1 2011 at 17:19

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

Zealint Feb 1 2011 at 13:06

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

lorc Feb 1 2011 at 12:51

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

hx0 Feb 1 2011 at 12:59

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

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

ariel32 Feb 1 2011 at 13:04

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

Zealint Feb 1 2011 at 13:09

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

fllln Feb 1 2011 at 13:05

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

Zealint Feb 1 2011 at 13:10

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

fllln Feb 1 2011 at 13:12

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

Bobylov Feb 1 2011 at 13:54

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

Zealint Feb 1 2011 at 14:01

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

hellman Feb 1 2011 at 14:13

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

CAH4A Feb 1 2011 at 17:15

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

jerom Feb 2 2011 at 13:52

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

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

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

Zealint Feb 2 2011 at 14:06

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

jerom Feb 2 2011 at 14:48

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

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