Блог Ромки

Пришло время тестить решения. Сначала рассмотрим лучшее решение (программа Werewolf’а, 303055 штрафных баллов) для задачи «Цифровая обработка». Я сгенерировал отдельный набор данных из картинок похожих на те что были в тестовом наборе, с различным уровнем шума от 2 до 20 процентов. Смотрим что получилось. Мое мнение — отлично!! Хотя на больших процентах мажет прилично. =) Чуть позже сделаю такую же табличку для нескольких лучших решений из топ20 и помещу её на http://zcontest.ru

Уровень шума	Оригинальная картинка	Картинка в серых тонах	Картинка после передачи	Картинка после работы программы восстановления	Штрафной балл = sqrt(сумма((Xoriginal-Xrestore)^2))
2%					483
3%					562

И ещё про планы:

После этого турнира будет проведен Open Contest 2007, с этими же задачами на английском языке. Просто 4 Fun, что бы чуть-чуть расшевелить застой на SPOJ.

После окончания соревнования выложу зашумленные картинки из задачи ZDIP и результаты — как программы победители справились с шумом. Сам ещё не смотрел и самому жутко интересно. Так же интересно перешагнет ли кто нибудь рубеж в 300000 баллов.

Тоже напишу про ZCon 2007. Вышел небольшой косячок с задачей ZDC. Judge очень глючный и переписать его (или просто отследить ошибки) я не могу, так как он доступен в бинарном виде. Написал автору и он обещал подсуетиться и исправить баги, но задаче уже три года и сможет ли он это сделать фиг знает. Знал бы не включал задачу в турнир.

Замеченые глюки:
1) Internal Error вызывается падением Judge. Скорее всего связано с каким то набором входных данных которые он не может корректно обработать.
2) Набор команд который должен давать одинаковый результат дает в итоге разный.

1) Вчера ходил на встречу в Горсеть по поводу поддержки соревнования. Само предложение зайти обсудить меня насторожило, потому что раньше эти вопросы решались просто по электронной почте. У них, как я понял, много всего поменялось, меня встретил какой-то мужик. Я с ним поговорил, рассказал, что да как, в общем, выложил всю информацию. Меня скептически выслушали, потом спросили, а какой от этого толк Горсети если это внешнее соревнование. Объяснил, что дополнительная реклама и к тому же мы не хотим ограничиваться только пользователями Горсети. Плюс мы просим поощрить только абонентов Горсети и не деньгами, а только внутрисетевыми бонусами. Мне прочли лекцию на тему, какая Горсеть стала большая и что абонентов у неё больше чем у всех остальных вместе взятых провайдеров в Зеленограде. Не смотря на это, он сказал, что поговорит по этому поводу с коммерческим директором. Хотя в том, что он таки организует поддержку, я сомневаюсь.
Последний год я вижу все меньше конкурсов в пределах Горсети, хотя раньше почти каждую неделю у них в новостях красовались объявления о новых соревнованиях и объявлялись победители старых. В общем, получился стандартный путь от маленькой «open-to-all» организации до большой безликой корпорации, которой некогда замарачиваться над маленькими проектами. Хотя посмотрим-с.

2) Из CQG мне пришел ответ, что они уже набрали полный состав программистов в свой штат и в мягкой форме сообщили, что соревнование им больше не интересно. Ибо они его рассматривали только, как возможность пригласить кого-нибудь на работу.

3) Обещались помочь с проведением соревнования Зеленоградская сеть Swamp и портал Zelenograd.ru за что им большое спасибо!

4) Выделил из своего кармана 100 баксов на призовой фонд, маловато конечно, но я коплю на HDTV. =)

5) Задачи готовы почти все, убил на них кучу времени. В большинстве из них надо ещё вылизать тексты и уточнить формулировки. Хочу также поблагодарить fdo_eq за часть составленных задач. Без него их количество было бы много меньше.

Жду всех программистов на соревновании http://zcontest.ru с 15 февраля по 15 марта.

Полностью подготовил 3 задачи для второго турнира zcontest. Есть идеи ещё как минимум для 8, но для большинства из них пока четко не ясна концепция подсчета очков. И парочка кажутся слишком похожими для одного контеста. А в одной из задач я в упор не могу придумать способ автоматизировать генерацию входных\выходных данных.
И не ждите тривиальных задач. Постараюсь сделать задачи максимально интересными, сложными и в тоже время доступными для решения любым человеком, естественно с посредственным результатом. =)
И ещё дилема надо ли запускать контест в сессию или летом? мб дождаться осени …

В свободное время готовлю задачи ко второму соревнованию по программированию. Пока есть идеи для 3-х задач, одна уже почти целиком готова и 2 полностью осмыслены, осталось только нагенерить тестовых данных. Собственно если у вас есть идеи каких нибудь интересных задач с неоднозначными решениями (challenge), то прошу высказываться в комментариях.
Поясню, что такое неоднозначные решения — это когда полностью и оптимально решить задачу невозможно из-за ограничений времени, но можно придумать алгоритм, который в короткие сроки даст ответ наиболее близкий к правильному. Ну и соответственно, надо знать способ как проверять и начислять очки за решение — часто это наиболее сложный момент.

Итак, что мы имеем:

2 геометрические задачки
2 задачи на графы
2 на теорию чисел
1 парсер + полиномы
3 задачки с неоднозначным решением
— решалка японских кроссвордов
— нахождение цифр чила Пи
— распознование образов

Ещё 2 задачи будут добавлены в процессе, мне кажется лучшими будут:
1) Задача использующая Convex Hull
2) Задача на строки
3) Задача на динамическое программирование + рекурсия (че нить вроде задачи о рюкзаке)
их сложность будет зависеть от того насколько будут успешно решаться уже добавленные задачи.

Вчера на мой запрос ответила администрация горсети. Обеспечат бесплатным траффиком + дадут новость на главной странице. Попросили макет новости и картинку … Вчера 2 часа сочинял новость, но все равно звучит КРИВО. Надеюсь до понедельника, что нибудь удобоваримое удастся родить. Дата старта уже стопроцентно известна: 15 февраля, ура товарищи. =)