Д.Г. Кобелев Внедрение системы проведения турниров по программированию ejudge в ШГПИ

Здесь мы обсуждаем правила подготовки и оформления ВКР, а также наиболее интересные и востребованные ВКР студентов факультета информатики.

Модераторы: xdsl, ustinova

Д.Г. Кобелев Внедрение системы проведения турниров по программированию ejudge в ШГПИ

Сообщение alx 19 мар 2010, 14:28

alx
Elite
 
Сообщения: 28
Зарегистрирован: 19 мар 2010, 09:53
Полное имя: Кудрявцев Александр Владимирович

Re: Д.Г. Кобелев Внедрение системы проведения турниров по программированию ejudge в ШГПИ

Сообщение xdsl 24 мар 2010, 12:51

Хотелось-бы подробностей: что конкретно сделано и где это посмотреть.
xdsl
 
Сообщения: 1236
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

Re: Д.Г. Кобелев Внедрение системы проведения турниров по программированию ejudge в ШГПИ

Сообщение alx 24 мар 2010, 15:38

Имеется ли возможность оценки скорости обработки данных в задаче.
alx
Elite
 
Сообщения: 28
Зарегистрирован: 19 мар 2010, 09:53
Полное имя: Кудрявцев Александр Владимирович

Re: Д.Г. Кобелев Внедрение системы проведения турниров по программированию ejudge в ШГПИ

Сообщение LMP 24 мар 2010, 20:36

kudravcev писал(а):Имеется ли возможность оценки скорости обработки данных в задаче.

у каждой задачи есть два лимита, помимо правильности - лимиты времени и памяти. в основном на выполнение алгоритма решающего даётся секунда(можно больше, если нужно), таким образом грамотно сформированные тесты, на которых будет запускаться решение и определяют количество баллов, которе будет дано за решение. в итоге получаем, чем оптимальнее алгоритм - тем больше баллов он получит.
LMP
Elite
 
Сообщения: 49
Зарегистрирован: 26 янв 2009, 22:05
Полное имя: Кобелев Денис

Re: Д.Г. Кобелев Внедрение системы проведения турниров по программированию ejudge в ШГПИ

Сообщение LMP 27 мар 2010, 10:25

Система доступна по адресу http://shgpi.edu.ru/ejudge/.

Общие правила:
1.) Вы должны быть зарегистрированиы в системе.
2.) Далее под своим логином нужно подтвердить своё участие в желаемом вам соревновании.

Краткое описание регистрации/входа:
Переходим по ссылке http://shgpi.edu.ru/ejudge/, выбираем любой открытый контест, выбираем "Создать учётную запись". Вводим желаемый логин, в качестве e-mail можно указать na. В случае успеха вам будет сгенерирован пароль(очень рекомендуется записать его). Вводим свой логин и пароль, заходим в "Настройки", и меняем пароль на желаемый (в случае смены пароля нужно будет заново авторизироваться). Подтверждием регистацию "[Подтвердить регистрацию]" и переходим по ссылке "Участвовать".

В случае если вы хотите поучаствовать в другом соревновании, то переходим по ссылке http://shgpi.edu.ru/ejudge/, выбираем желаемое соревнование, авторизируемся, подтверждаем регистрацию, участвуем. Успеха :)
LMP
Elite
 
Сообщения: 49
Зарегистрирован: 26 янв 2009, 22:05
Полное имя: Кобелев Денис

Re: Д.Г. Кобелев Внедрение системы проведения турниров по программированию ejudge в ШГПИ

Сообщение xdsl 27 мар 2010, 11:19

Попробуем, потестим ;)
xdsl
 
Сообщения: 1236
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

Re: Д.Г. Кобелев Внедрение системы проведения турниров по программированию ejudge в ШГПИ

Сообщение Anastasia 29 мар 2010, 21:29

у меня совсем не умный вопрос, но все же безумно интересно: почему система так называется?...
Anastasia
 
Сообщения: 4
Зарегистрирован: 27 мар 2010, 17:30
Полное имя: Луканина Анастасия Анатольевна

Re: Д.Г. Кобелев Внедрение системы проведения турниров по программированию ejudge в ШГПИ

Сообщение LMP 29 мар 2010, 21:49

judge - судья, e - думаю сокращение от слова электронный, получаем электронного судью :)
LMP
Elite
 
Сообщения: 49
Зарегистрирован: 26 янв 2009, 22:05
Полное имя: Кобелев Денис

Re: Д.Г. Кобелев Внедрение системы проведения турниров по программированию ejudge в ШГПИ

Сообщение xdsl 30 мар 2010, 08:07

Денис, признайтесь честно, на турнире http://shgpi.edu.ru/ejudge/cgi-bin/new-register?contest_id=2 в задаче "Игра в слова" последние 4 теста - это крэш-тесты? Мне уже действительно любопытно стало. Я вчера оптимизировал свое решение, на 9 словах, которые начинаются и заканчиваются одной буквой, добился генерации 362880 выходных строк за 0.7-0.8 секунды, причем большая часть этого времени уходит на генерацию выходных данных, а не на сам алгоритм, так-что путей дальнейшей оптимизации не вижу. Однако проверка на Ваших последних четырех тестах опять показывает превышение лимита времени. :(
xdsl
 
Сообщения: 1236
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

Re: Д.Г. Кобелев Внедрение системы проведения турниров по программированию ejudge в ШГПИ

Сообщение LMP 30 мар 2010, 09:28

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

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

согласитесь, что тесты должны быть и простые и сложные. если появится решение, которое будет быстрее моего, то и тесты ещё усложнятся. считаю это нормальным развитием задачи :)
LMP
Elite
 
Сообщения: 49
Зарегистрирован: 26 янв 2009, 22:05
Полное имя: Кобелев Денис

Re: Д.Г. Кобелев Внедрение системы проведения турниров по программированию ejudge в ШГПИ

Сообщение xdsl 30 мар 2010, 12:03

Хм, значит подход "в лоб" неприменим, придется оптимизировать не формирование больших объемов выходных данных, а сам алгоритм перебора. У меня, кстати, тоже "левые" цепочки отбрасываются, но, похоже, не все.

Ах да, а как Ваш алгоритм реагирует на 9 слов (10 символов и более), начинающихся и заканчивающихся на одну и ту-же букву?
xdsl
 
Сообщения: 1236
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

Re: Д.Г. Кобелев Внедрение системы проведения турниров по программированию ejudge в ШГПИ

Сообщение LMP 30 мар 2010, 12:41

набор входных данных:

Код: Выделить всё
abcdefghijklmna
abcdefghijklma
abcdefghijkla
abcdefghijka
abcdefghija
abcdefghia
abcdefgha
abcdefga
abcdefa

на машине где я проверял своё решение ушло 0.9 секунд, в результате - 362880 цепочек.
LMP
Elite
 
Сообщения: 49
Зарегистрирован: 26 янв 2009, 22:05
Полное имя: Кобелев Денис

Re: Д.Г. Кобелев Внедрение системы проведения турниров по программированию ejudge в ШГПИ

Сообщение Vladislav_133 30 мар 2010, 17:43

И меня задели. Начал свою программу на солвере провярять, для 9 перестановок дает ошибку
Fatal error: Allowed memory size of 5242880 bytes exhausted (tried to allocate 4194284 bytes) in /var/www/apache2/html/solver/0.1b/driver/task_classes.php on line 88
Не понятно в чем дело. Памяти я использую мало. Никаких динамических алокэйтов (только в начала выделяю чуть чуть).
Как это понять. Дома все работает. Генерирует и 9! и 10! и 11!. рекурсия, наверное, все сжирает?
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Д.Г. Кобелев Внедрение системы проведения турниров по программированию ejudge в ШГПИ

Сообщение LMP 30 мар 2010, 19:05

насколько я знаю работу солвера, он запускает ваше решение, потом считывает результат. возможно именно при считывани результата и выдаётся эта ошибка, в пхп есть ограничение на используемую память. я считаю что проблема в настройке пхп. с другой стороны, 9! это очень много текста, и не стоит столько выводить, возможно стоит сделать ограничение в решении на солвере.
LMP
Elite
 
Сообщения: 49
Зарегистрирован: 26 янв 2009, 22:05
Полное имя: Кобелев Денис

Re: Д.Г. Кобелев Внедрение системы проведения турниров по программированию ejudge в ШГПИ

Сообщение xdsl 31 мар 2010, 08:26

Нашел еще один неоптимальный участок кода в своем решении, заменил, теперь проходит 8 тестов из 10. Пока дальнейших путей оптимизации не вижу, кроме предварительной сортировки исходных данных по убыванию размера строк, а также выделения непересекающихся списков строк, которые можно обрабатывать отдельно друг от друга. Однако указанные варианты - лишь частные решения, произвольный набор в 100 исходных строк они не помогут обработать.
xdsl
 
Сообщения: 1236
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

Re: Д.Г. Кобелев Внедрение системы проведения турниров по программированию ejudge в ШГПИ

Сообщение Vladislav_133 31 мар 2010, 08:40

Дм. Анатольевич, так предложение ведь дельное. Надо как-то ввести ограничение на количество выводимых строк. Тогда, наверное, и ошибки не будет.
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Д.Г. Кобелев Внедрение системы проведения турниров по программированию ejudge в ШГПИ

Сообщение xdsl 31 мар 2010, 12:01

На самом деле - надо ввести ограничение на кол-во выводимых строк в условие задачи. И под это условие уже и переписать решение.
xdsl
 
Сообщения: 1236
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

Re: Д.Г. Кобелев Внедрение системы проведения турниров по программированию ejudge в ШГПИ

Сообщение Vladislav_133 31 мар 2010, 12:23

Хм, возможно. Ну тут теряется какая-то универсальность. Скажем, может быть порциями выводить в солвере.
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Д.Г. Кобелев Внедрение системы проведения турниров по программированию ejudge в ШГПИ

Сообщение xdsl 31 мар 2010, 13:57

Если выводить порциями, придется переписывать всю систему ввода-вывода солвера, что очень не хочется. Тем более, что сбои идут только на действительно больших объемах, которые не подходят для веба и наших скоростей. Например, для
Код: Выделить всё
abcdefghijklmna
abcdefghijklma
abcdefghijkla
abcdefghijka
abcdefghija
abcdefghia
abcdefgha
abcdefga
abcdefa
получаем порядка 38МБ результата.

Вместо этого, мы можем внести ограничение в условие задачи: "... найти первый десяток (сотню, тысячу) строк с максимальным кол-вом символов ...".
xdsl
 
Сообщения: 1236
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

Re: Д.Г. Кобелев Внедрение системы проведения турниров по программированию ejudge в ШГПИ

Сообщение xdsl 31 мар 2010, 14:03

Кстати, Владислав Юрьевич, ваше решение в солвере дает странный результат на следующем тесте:
Код: Выделить всё
aa
ab
ac
ad
ba
bb
bc
bd
da
db
dc
dd
ea
eb
ec
ed
ef
eg
ga
gb
gc
gd
aa
ab
ac
ad
aa
ss
xx
vv
nn
mm
aa
aa
zaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaz
xdsl
 
Сообщения: 1236
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

Re: Д.Г. Кобелев Внедрение системы проведения турниров по программированию ejudge в ШГПИ

Сообщение Vladislav_133 31 мар 2010, 14:25

там ограничение на длину строки есть
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Д.Г. Кобелев Внедрение системы проведения турниров по программированию ejudge в ШГПИ

Сообщение LMP 31 мар 2010, 14:41

xdsl писал(а):Вместо этого, мы можем внести ограничение в условие задачи: "... найти первый десяток (сотню, тысячу) строк с максимальным кол-вом символов ...".

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

и в решении на солвере это проверять. в случае, если на выходе более ста строк, то сообщать пользовотелю о некоректных входных данных.
LMP
Elite
 
Сообщения: 49
Зарегистрирован: 26 янв 2009, 22:05
Полное имя: Кобелев Денис

Re: Д.Г. Кобелев Внедрение системы проведения турниров по программированию ejudge в ШГПИ

Сообщение Vladislav_133 05 апр 2010, 09:37

Выслал Дм.Ан. вариант программы с возможностью контролировать количество выводимых строк, а также рабатающей в двух режимах: максимум по количеству слов и максимум по количеству букв.
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Д.Г. Кобелев Внедрение системы проведения турниров по программированию ejudge в ШГПИ

Сообщение xdsl 05 апр 2010, 10:12

Вставлю решение в Solver. Кстати, по дефолту какой режим работы программы?
xdsl
 
Сообщения: 1236
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

Re: Д.Г. Кобелев Внедрение системы проведения турниров по программированию ejudge в ШГПИ

Сообщение Vladislav_133 05 апр 2010, 10:19

по дефолту "по словам"
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

След.

Вернуться в Выпускные квалификационные работы

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1

cron