Сервер олимпиад

admin · Добавлено: 26.02.2009 13:07:40

Обсуждаем олимпиаду по параллельным вычислениям. Все вопросы по организации - здесь.

jackb · Добавлено: 02.03.2009 18:39:14

У меня несколько вопросов:

1) Мне непонятно, причем тут вообще в этой олимпиаде параллельные вычисления? Ни в правилах, ни в условиях задач об этом нет ни единого слова (кроме заголовка). Да и предложенные задачи совсем не по теме.

2) В заданиях нигде не указаны никакие ограничения - ни на входные данные, ни на времени или память, отводимые для каждого теста. Вы предлагаете участникам их угадывать, так что ли?

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

4) Условие задача 5 мне вообще не понятно. Где это дана та электрическая схема? Я не вижу в условии никакой схемы. Соответственно, описание формата входных данных выглядит какой-то чепухой для меня.

admin · Добавлено: 02.03.2009 20:21:30

1. Параллельные вычисления можно использовать в каждой задаче. Преложенные задачи соответствуют теме.
2. В правилах учета решений (2 стр.) написано "Марафон-турниры отличаются от традиционных олимпиад тем, что могут не иметь ограничений на входные данные." Время должно стремиться к минимуму, память аналогично. При превышении вы получите Runtime Error. Угадывать можно, поскольку количество попыток не учитывается.
3. Нецелые числа содержат ".". Точка, как и скобки не входят в состав разрешенных символов. Точность до десятых.
4. (соединение слева)--[Резистор]--(соединение справа)

Отредактировано модератером

jackb · Добавлено: 02.03.2009 20:53:46

>1. Параллельные вычисления можно использовать в каждой задаче.
Каким же это, интересно, образом их можно использовать? У вас же никакие библиотеки не разрешены - ни OpenMP, ни pthreads, ни win32 api. MMX/SSE/SSE2 интринсики тоже не разрешены (не переданы нужные флаги gcc). И непонятно даже на каком оборудовании тестируются решения - что за процессор, сколько ядер.

>2. В правилах учета решений (2 стр.) написано
>"Марафон-турниры отличаются от традиционных олимпиад
>тем, что могут не иметь ограничений на входные данные."
Ну и какой в этом смысл? Отсутствие конкретных ограничений лишь только раздражает. Все нормальные контесты указывают ограничения на входные данные.

>Время должно стремиться к минимуму,
В правилах, запихнутых в файл с условиями, между прочим сказано: "Максимальное время работы программы в секундах указывается для каждой задачи." Вот где, скажите, оно указывается?

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

admin · Добавлено: 02.03.2009 21:38:09

Пробуйте, смотрите за изменениями на сайте.

Весь смысл в написании универсального решения.

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

jackb · Добавлено: 03.03.2009 09:39:15

Еще несколько вопросов:

1) На каком конкретно железе тестируются решения (какой процессор и сколь на нем ядер)? Операционная система 64-битная?

2) Какой gcc используется - mingw gcc, cygwin или еще какой-то?

3) Каким конкретно образом входные данные подаются на stdin? Перенаправлением файлов, через pipe, или еще как-то? Я могу mmap-нуть весь stdin в память (ф-цией MapViewOfFile в win32 api, или mmap(1) в cygwin и POSIX)?

4) Допускается ли использование ассемблерных вставок в программах на C++?
(Если нет, то почему тогда отключена оптимизация в gcc? - разница в скорости выполнения без нее очень существенна)

5) Разрешено ли использование библиотеки pthreads?

6) Разрешено ли использование функций Win32 API? (CreateThread, например)

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

edel · Добавлено: 03.03.2009 15:02:21

на сколько помню:

2 - раньше был gnu cc++ mingw. в правилах сказано:
Список компиляторов и их командных строк:
Borland Delphi 6.0 - dcc32.exe -cc %1
GNU C/C++ - g++.exe -o %1

3 - не имеет значения. делайте printf при выводе,
MapViewOfFile это специфика платформенной реализации.
Каким это образом stdin преобразуется в HANDLE для файла? Ересь.
в задачах обычно необходимо найти красивое алгоритмическое решение, а не платформенное.
Первый раз слышу что pipe и stdin можно связать.
Если пайм двусторонний, то чтение идет с него и запись в него, а не с stdin. потому само собой перенаправление. как именно? это не ваше дело.
чтение данных указано в правилах:
readln , gets и т.д.
читайте правила еще раз.

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

5,6,7 ... ? самому интересно.

jackb · Добавлено: 03.03.2009 16:25:24

>3 - не имеет значения. делайте printf при выводе,
>MapViewOfFile это специфика платформенной реализации.
>Каким это образом stdin преобразуется в HANDLE для файла? >Ересь.

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

Ввод/вывод с помощью mmap/MapViewOfFile осуществляется намного быстрее чем через традиционные буферизованные интерфейсы программирования, такие как процедуры scanf, gets, readln, и т.д.

>Первый раз слышу что pipe и stdin можно связать.
Конечно же их можно связать! Пайплайны в шеллах именно таким образом и делаются - открывается односторонный пайп, вход которого прицепляется к stdout одной программы, а выход к stdin другой.
Если ввод в вашем тестере реализован этим способом, то одним из его последствий является невозможность использования mmap для чтения входа.

>4 - точно нет асма. может нарушить работоспособность
> системы, как и на любых тестерах такого уровня защиты.

Ну значит очень плохо ваша система тестировано построена, раз какие-нибудь произвольные команды на asmе могут "нарушить [ее] работоспособность". На других нормальных тестерах с которыми я работал такое не может произойти. Насчет windows-тестеров ничего сказать не могу, но я точно знаю, что, например, на базе linux/freebsd систем очень легко построить тестер, устойчивый к любым атакам такого рода.

К тому же, запрещая асм ваша система все равно останется уязвимой к этим атакам - произвольный код можно зашить в программу в виде массива данных, и выполнить его, вызвав этот код через указатели на функцию.

Без инлайнового асма нельзя воспользоваться наборами инструкций MMX/SSE/SSE2/SSE3. А если и эти инструкции запрещены, и потоки запрещены, то что же тогда в этом контесте остается от параллельных вычислений??!

> оптимизация... зачем? соревнование идет на с самим собой
> а с другими участниками. все в одинх условиях.

Запрещая оптимизацию вы сильно ущемляете участников использующих C++ с STL - библиотека STL очень сильно заточена под оптимизация компилятора, ее производительность без и с оптимизация различаются почти на порядок...

edel · Добавлено: 03.03.2009 16:45:35

...есть идеи построения защиты от атак, когда
байтовый массив превращается в асм-функцию?...

не все способны на такое.
защита от шеллкода под виндой это конечно вопрос...

edel · Добавлено: 03.03.2009 16:46:58

можно конечно юзать DEP...

Сервер олимпиад

Ставропольский государственный университет

Server Off-Line

Форум