Уже совсем скоро в офисе компании КРОК состоится финал чемпионата. Позади день с пробным туром и Code Game Challenge. В суровой борьбе убедительную победу в Code Game Challenge одержал tourist!

Кроме того сегодня состоится онлайн-раунд по задачам финала, этот раунд начнется в 19:00 и будет идти 2.5 часа. По результатам раунда будет обновлен рейтинг. Обратите внимание, что к этому времени будут доступны результаты финала, так что участники онлайн-раунда будут лучше представлять предполагаемую сложность задач.

Всем удачи!

Соревнование закончено. Победителями стали:

• tourist
• Egor
• eatmore

Полные результаты

На самом деле в КРОК я и MaximShipko приехали еще вчера. За это время, совместно с кроковцами, успели настроить 40 компьютеров в учебном классе (даже как-то жалко, что большинство будет использовать ноуты), настроить инфраструктуру Code Game Challenge и готовы к появлению участников.

Совсем скоро состоится [contest:307]. Не стоит удивляться, если часть функционала сайта будет ограничена. В настоящий момент основная цель — основное онсайт-мероприятие.

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

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

12-го мая 2013 в 00:00 (да-да, в полночь!) состоится Testing Round 6. Цель этого раунда — хорошенько протестировать платформу. Недавно были сделаны некоторые улучшения/нововведения. Все изменения лежат в недрах бэкенда Codeforces и не будут сильно заметны участникам, однако они затрагивают довольно большое количество кода.

Приглашаю вас принять участие. Раунд будет происходить по схеме Div.2 + неофициальное участие Div.1. Он будет состоять из четырех-пяти задач, как определенная разминка — будет интересно всем. Я попрошу не участвовать тем, кто живет в Саратове — вам эти задачи могут оказаться знакомы. Претесты в задачах будут необычно слабыми, чтобы спровоцировать побольше взломов. Конечно, раунд не будет влиять на рейтинг.

Спасибо всем, кто примет участие!

P.S. Такое странно время выбрано не случайно — в выходные лучше всего работать по ночам!

Ура-ура! Завершив многоходовую комбинацию я-Кормен-ralekseenkov, мы готовы отдать должное героям 2012-го года. В этом году (спасибо, Томас!), лауреаты Медали Кормена получат не только медали, славу и почет, но и новую книгу Томаса Кормена "Algorithms Unlocked" с личной подписью автора!

Лауреатами Медали Кормена за 2012-ый год стали:

• tourist (Геннадий Короткевич) — Codeforces Best Participant 2012
  Геннадий удерживает первое место в рейтинге Codeforces, продолжает активно участвовать и уже не всегда даже третье место в раунде приносит ему плюс к рейтингу. Желаем Геннадию новый побед, тем более финал ACM-ICPC 2013 ведь так скоро!
• witua (Виталий Герасимов) — Codeforces Best Problemsetter 2012
  В 2012-ом году Виталий неоднократно радовал нас интересными задачами. Благодаря ему, мы отлично знаем всевозможные свойства счастливых чисел и маленьких слоников. Спасибо Виталию за отличные задачи!
• Nickolas (Мария Михайлова) — Codeforces Spirit of Community 2012
  Мария — автор необычных раундов, активный блоггер 2012-го года, удостоена новой номинации. Затеи Марии, нестандартные и яркие, сделали жизнь сообщества веселее и разнообразнее.
• Alex_KPR (Александр Куприн) – Codeforces Best Blogger 2012
  Все мы с удовольствием читали повествования Александра с различных значимых событий спортивного программирования 2012-го года.

Напоминаем, что Медали Кормена присуждаются уже третий год. [tourist] уже третий год подряд становится лучшим участником, а Alex_KPR – лучшим блоггером в оба года присуждения этой номинации. В моей любимой номинации «Лучший автор задач Codeforces» победителями становились: в 2010-ом году natalia (Наталья Бондаренко), а в 2011-ом году Ripatti Артём Рипатти.

Очень надеемся, что лауреаты прошедшего года будут нас радовать своими талантами и в 2013-м году.

Как известно майские праздники — это праздник труда и трудящихся. Поэтому 2-го мая бездельничать не пришлось (надо же соответствовать названию праздника). Встречайте новые языки на Codeforces:

• Python 3 (3.3.1)
• MS C# .NET 4
• Go (1.1 RC1)

Я даже предпринял попытку настроить Clojure, но выяснилось, что благодаря его динамической натуре и прочим AOT, простейшее решение A+B работает на нем около 1 секунды. Видимо как-то можно компилировать решения прям в байткод сразу, но пока я не разобрался. Может есть специалисты?

А пока раунд далеко я призываю вас попробовать новые языки.

С праздником!

P.S. В качестве дополнительного бонуса — Python 2 был обновлен до 2.7.4.

Совсем скоро стартует Квалификационный раунд Всероссийского Открытого Чемпионата по программированию "КРОК-2013". Раунд будет идти двое суток, мы надеемся каждый сможет найти удобное себе время для участия. Этап начнется 13 апреля в 00:00. Общий список зарегистрированных на Чемпионат доступен по ссылке.

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

Раунд продлится 48 часов, но это не значит, что мы призываем вас все это время провести за решением задач. Мы надеемся, что большинство участников справятся с задачами (или с большинством задач) за более короткий срок. Такая длительность раунда выбрана для того, чтобы каждый нашел удобное время для участия.

До окончания раунда категорически запрещается публиковать где-либо условия задач/решения/какие-либо мысли и соображения о них. Запрещено общаться на тему задач, обсуждать условия и проч. Будьте честными и пусть в Раунд 1 пройдут достойные. Как только квалификация будет завершена, можно будет обсуждать задачи и решения.

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

P.S. В этом раунде допускаются к участию только зарегистрированные участники Чемпионата. Зарегистрироваться для участия в Чемпионате можно здесь. Особо расторопные участники успели зарегистрироваться до внедрения такой проверки, поэтому некоторые регистрации придется аннулировать. Кажется, это не принесет вам сложности — так как впереди еще двое суток.

UPD: Тестирование завершено. По предварительным данным все участники с не менее чем 950 баллами проходят в Раунд 1. Граница может быть немного изменена из-за удаления читеров.

В связи с тем, что у TopCoder сорвалось проведение TCO 2013 Round 2A, а перенесли они его со снайперской точностью на запланированный нами ранее Codeforces Round #177, мы решили подвинуть наше мероприятие. Признаюсь, моим первым побуждением было оставить всё как есть — TopCoder прекрасно знал о Codeforces Round 177, и я не могу одобрить такой подход к решению своих технических сложностей. С другой стороны, сообщество, а особенно автор предстоящего раунда, уважаемый witua, не виноваты — вам хочется участвовать, а автору интереснее, когда раунд собирает аншлаг. К тому же, координатору задач Gerald-у пришлось бы несладко, разрываясь между работой и TCO. Поэтому Codeforces Round #177 сдвинут на время запланированное для раунда #178, а тот будет перенесен чуток вперед.

Мы приносим извинения за изменения в расписании. Надеемся, увидеть вас среди участников Codeforces Round #177. Будет весело!

Ну круто-то же! Сотрудники КРОК не перестают меня удивлять инициативными подходом к делу. На этих роликах вы увидите не нанятых актеров, а сотрудников КРОК. Признаюсь, я искренне по-хорошему удивился актерским способностям Георгия, Марии, Михаила — все они непосредственные организаторы олимпиадных инициатив КРОК.

Кстати, если вы знаете что-то подобное — делитесь в комментариях. Так же интересно было бы собрать идеи сюжетов для подобных роликов — о где ты, креативный олимпиадник?

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

Итак, в добавил тренировку 2012-2013 Московская олимпиада школьников по информатике, 10-11 класс. Вот ссылка на официальную страницу и результаты 10-11 классов. Поздравляю победителя Павла pashakovalenko Коваленко!

Студентам Варшавского университета дали задание по популяризации алгоритмов в Сети. Вот что получилось.

Давайте делиться впечатлениями о прошедшем отборе.

Самый забавный момент был у меня, когда за 10 минут до конца моя C падала с assert-ом, что говорило о том, что одна структура данных считается с отличием от наивного решения. Поискал баг, не нашел. Закомментил assert и скачал input. Не знаю чем закончится, но на инпутах rng_58 и Petr мое решение выдает ответы как у них :)

Welcome to the contest of Saratov State U on Petrozavodsk Winter Training Camp 2012-2013. This contest was prepared with diligence and love by jury team of ACM-ICPC NEERC Subregional (Saratov) Contest. Here is the complete list of writers:

• MikeMirzayanov
• Nerevar
• RAD
• e-maxx
• natalia
• NALP
• DmitryKlenov
• Dmitry Mescheryakov
• DStepanenko

Thanks to all of them!

All the authors invite you to take part in the contest virtually in Gym, if:

• You didn't take part in it previously
• You (or your team) is high skilled that you will take part (or took part) on ACM-ICPC World Finals or other high-level competitions. The problemset seems to be hard for not experienced participants.

Hope, you will enjoy the contest!

Contest link: 2012-2013 Зимние Петрозаводские сборы, Контест Саратовского ГУ (XIII Открытый Кубок, Гран-При Саратова).

Всем привет!

Получилось ли вам провести январь так же продуктивно, как это сделали мы? Вот небольшой список заметных пользователям изменений/нововведений:

• Теперь тренерами могут стать не только красные, но и те, кто обладает оранжевым цветом хэндла, участвовал в офиц. соревновании Codeforces не более полугода назад и принял участие не менее чем в 30 рейтинговых соревнованиях Codeforces). Это изменение увеличивает количество потенциальных тренеров примерно вдвое. Так что мы приглашаем вас к участию в тренировках уже в новом статусе!
• Добавить контест из Polygon в Тренировки стало совсем просто! Достаточно скопировать данные из contest.xml из интерфейса контеста в системе Polygon в contest.xml в папке sandbox контеста в Тренировках (используйте FTP).
• Внедрена защита от потери данных в формах проектов Codeforces и Polygon. Теперь в полях ввода для текста справа сверху появляется полупрозрачная кнопка «Черновики», с помощью которой можно посмотреть (или выбрать) какие-то предыдущие редакции текста. Сохранение в эти черновики происходит автоматически. Теперь в случае неожиданного падения браузера или потери сессии ничего страшного не случится – ваш текст будет возможно восстановить из черновиков.
• Проделана работа по внедрению проталкивания событий о тестировании из системы в браузер, что видно на странице «Статус». Работа пока не закончена, есть свои заморочки, но базово система работает.
• Обновлен testlib до 0.8.7: улучшена производительность функции ensure(), readStrictDouble больше автоматически не определяет как невалидное число, состоящее более чем из 20-ти цифр, исправлены warnings при компиляции, починена компиляция в некоторых экзотических случаях.
• В системе Polygon улучшена производительность в случае задачи с большими ручными тестами.
• Условия контестов и задач в системе Polygon теперь имеют логичные URLs.
• Исправлены ошибки, связанные с тем, что в некоторых старых задачах стандартный чекер автоматически обновляется, но не обновляется testlib. Это приводит к невозможности использования чекера в такой задаче, так как он не компилируется с устаревшим testlib.h. На всякий случай внедрена политика автообновления для testlib, теперь совсем просто его можно обновить.
• Если решение в системе Polygon помечено как Main или Correct, но получает OK на тесте со временем более половины от ограничения по времени, то такая ситуация подсвечивается в invocations. Аналогично, подсвечивается ситуация, когда TL-решение получает TL, но при этом получает OK при удвоенном ограничении по времени.
• В дескрипторе задачи в системе Polygon добавлен атрибут sample для теста. Он имеет значение sample="true", если это тест из условия. Этот атрибут опциональный, его отсутствие эквивалентно sample="false".
• Обновлены версии компиляторов до крайне свежих.

На последнем тестовом раунде (Codeforces Testing Round 5) в качестве сложной задачи была предложена моя задача 267C - Berland Traffic. Задача интересная и, как показали результаты, непростая. Придумал эту задачу я довольно давно, а дал ее (с другим названием и легендой) на школьные летние сборы в Малоярославце (2003 года).

Сегодня испытал забавное ощущение, заметив в контесте Варшавского университета Петрозаводских зимних сборов 2012 задачу "I. Uniform Flow". Глянул тесты — и тесты мои :-) Забавный круг совершила эта задача!

P.S. Кстати, задачу эту я считаю довольно полезной. Полагаю, схожие идеи иногда могут встретиться и в других задачах.

12-го января 2013 в 19:00 состоится Codeforces Testing Round 5. Цель этого раунда — хорошенько протестировать платформу. Недавно были сделаны некоторые улучшения/нововведения. Из того, что видно участникам — это настоящий realtime статус. Да, уже сейчас, если вы перейдете на страницу статуса архива, то сможете увидеть, что он обновляется самостоятельно без каких-либо перезагрузок страницы. Сделано это в ключе модных realtime-технологий — обновления проталкиваются к вам в браузер через websockets или другим comet-подобным образом. Конечно, никакого polling-а сервера.

Кроме того, на сервере было обновлено разное ПО, а Codeforces пересобран на Java 7.

Приглашаю вас принять участие. Раунд будет происходить по схеме Div.2 + неофициальное участие Div.1. Он будет состоять из трех несвежих задач, но как определенная разминка — будет интересно. Уверен, многим задачи покажутся интересными. Претесты в задачах будут необычно слабыми, чтобы спровоцировать побольше взломов. Конечно, раунд не будет влиять на рейтинг.

Спасибо всем, кто примет участие!

Этот текст был написан мной около 10 лет назад, сразу же после окончания выступлений нашей команды Saratov SU 3. Я нашел его случайно на винчестере, который подписан маркером "2002-2005". Надо сказать, что рысканье по старым файлам — та еще археология.

Команда Saratov SU#3 или как это было

Как все начиналось? Это был май 2000 года – то самое время, когда сессия еще не началась, а погода уже установилась. В тот май на каждом углу на проспекте Земфира пела о ромашках и кораблях.

Говорят, Илья (будущий капитан команды) долго советовался с нашими тренерами по поводу состава. После какого-то семинара, где я рассказывал о построении перестановок и о таблицах инверсий, Илья и Павел Комков подошли ко мне и предложили стать членом новой команды. Для меня это было трудное решение перейти в другую команду, так как я сам был капитаном Saratov SU#4 (1999/2000) и к тому же считал этот состав вполне перспективным.

Решилось все просто: с одной стороны мы договорились попробовать поучаствовать вместе (Илья, Андрей Лазарев и я) в наступающем интернет-соревновании IPSC 2000. С другой стороны Илья Агошков, член моей команды, пропустил еще пару тренировок, что подтвердило систему его посещений: одна из пяти – уже много.

19 мая 2000 года в лаборатории номер 81 корпуса «следующий за моргом» состоялось первое соревнование, которое мы писали вместе. Назывались мы тогда Saratov SU#1 и заняли почетное 27-е место. До сих пор вспоминается, как после безуспешных попыток решить одну из задач, Андрей понял, что она не работает на 3 тестах. На каждый из тестов надо было выводить слово «YES» или «NO». Всего-то 23 вариантов перебрать! С седьмой попытки, к нашей радости, мы ее сдали. Уже на летних тренировках было официально объявлено о новом составе, и наша команда получила скромное имя Saratov SU#3.

Так как Андрей уехал на турбазу отдыхать, было решено установить в команде систему штрафов за пропуск или опоздание. По приезду Андрея ждал сюрприз!

В то лето я много решал один, по ночам – это стало правилом. Я с ностальгией вспоминаю то время, когда я писал дома в ночь по тренировке. Тогда было время больших открытий: мы придумывали, как решать новые задачи, составляли методы. Сейчас эти задачи кажутся смешными, методы вспоминаются в плохих снах.

Летом мы писали много интернет-соревнований на небезызвестном испанском сервере, а так же на только что появившемся, уральском. Мы шутили: места мы занимаем хорошие, но невысокие. На тренировках мы сразу расставили все точки над «ё» и лишь единожды уступили первое место. Илья бы добавил: «Да ладно, мы тогда часа на три раньше ушли, на пляж отправились». Тем летом я последний раз поговорил с Бабенко Максимом в Саратове. В следующий раз мне удалось это сделать только в Гонолулу. Он был первым саратовским школьником на Международной олимпиаде по информатике. Закончив ФТЛ №1, он уехал учиться в МГУ. Пару слов о нем: когда я учился решать квадратные уравнения, он брал интегралы, когда я научился брать интегралы, он пытался аналитически продолжить на R функцию вида N^N^...^N, высота степени равна N.

А потом был четвертьфинал. Это был своеобразный тест на прочность нашей команды. В тот год приехали две команды из Нижнего Новгорода – в одной был Владимир Мартьянов (четырежды чемпион России среди школьников, дважды чемпион мира), и Михаил Баутин (абсолютный чемпион мира 2000). Баутина мы называли про себя не иначе как: «ну этот … 700 баллов из 700», вспоминая его выступление на международной олимпиаде.

Тест на прочность наша команда прошла, соревнование провалила. Мы заняли второе место. На следующий день Андрей бил себя в грудь и кричал: «Да B простая задача! Ее надо было решать!». Я ему в ответ: «Я и говорю в E все понятно!» Хотя, говоря по правде, первое место мы бы все равно не заняли. Уж больно резко решал все «700 баллов из 700».

Следующим барьером был полуфинал. Именно перед ним Илья произнес ту фразу, которую он так не любит вспоминать: «Если SU #1 обойдет нас, я повешусь на своем собственном ремне». Готовились мы день и ночь. Андрей придумывал пачками задачи, я пытался их пачками решать. Решали все что видели, а на глаза попадалось многое.

В финал в тот год выходило команд 6 и я помню те долгие часы телефонных разговоров между мной и Андреем: «Ну ты посчитай: Москва, ладно, это раз. Далее Питер, ну там два вуза. Еще Нижний Новгород. А остальные? Что мы Урал никогда не обходили? Или Беларусь?»

К полуфиналу 2000 года нас уже знали…

Долгими зимними вечерами я вспоминаю задачу G. Ее решили все из первой тридцатки, кроме нас. Это был удар. Saratov SU#1 заняла 16-е место, мы 18-е. Кто-то вспомнил про ремень. Далее был период осмысления. Он продлился до середины февраля 2001. Только тогда наша команда собралась снова. Было время, когда я думал, что команда Saratov SU#3 должна умереть. В феврале я думал уйти из команды, решив, что я слабое звено. К счастью, мое решение так и осталось неосуществленным.

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

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

К полуфиналу 2001 года нас уже знали…

Недавно я узнал, что Матвей Казаков (один из организаторов полуфинала) очень долго, с любовью подбирал призы для второго места на полуфинале. Он считал, что оно достанется их команде (ИТМО #1), нам он отдавал первое.

Не вышло: споткнулись на одной задаче, не проявили прыти в другой – в итоге 2 место. На самом деле это был триумф! Уже вице-чемпионы России, предстоящая поездка в Гонолулу (США, Гавайи) – все это могло вскружить голову.

Во время подготовки к финалу 2002 на тренировках мы выступали стабильно. В интернет-соревнованиях расстраивались, когда не брали первые места.

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

Сам ход соревнования поразил нас, наверное, в первую очередь. Чем? Все было так, как на тренировках. Мы быстро сдали задачи попроще, вышли на первое место (первое в мире, я уже верю с трудом), решали задачи потруднее. За час до конца мы были на втором. Я помню тот миг, когда, отсылаю последнюю задачу, мы знали что, если она пройдет, титул чемпионов мира наш. Андрей нажал «Отправить», все ждали. Нам не повезло, пришел «Неправильный ответ», задачу не зачли. Оставшиеся минут пятнадцать мы тщетно пытались найти ошибку. Чемпионы Европы, серебряная медаль чемпионата мира, 6 место в мире. Вот тот набор титулов, с которым мы вернулись в Саратов. Мы более двух часов были на первой строчке. Так закончился сезон 2001/02.

Опущу описание тренировок перед четвертьфиналом 2002, а скажу лишь, что на самом соревновании у нас было лишь 3-е место. Команда Saratov SU#2 заняло второе, после нижегородцев, которые стали чемпионами подрегиона.

На полуфинале у нас тоже было третье. Москва показала себя – опережая по ходу соревнования всех на две задачи, они решили весь комплект задач за час до конца. Вторым был Нижний Новгород. ИТМО (Санкт-Петербург) был лишь шестым.

Итак, в сборную России вошли команды следующих ВУЗов: Московский ГУ, Нижний Новгород ГУ, Саратов ГУ, СПб ГУ, ИТМО (СПб), Вологодский педагогический, Самарский Университет Марины Наяновой.

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

К середине соревнования мы сдали две задачи и написали еще пару, в которых посадили глупые ошибки и их не принимали. Все казалось если не катастрофой, то хотя бы бедствием. Наверное, мы справились с ситуацией только благодаря большому тренировочному и соревновательному опыту. Ошибки нашли, придумали, как решать другие задачи. Некоторая интрига завернулась в конце соревнования, когда до хорошего места нам не хватало одной решенной задачи. Оставалась, видимо, одна задача, которую было реально решить за оставшиеся сорок минут. Ее решило большое число команд, но как ее решать мы не знали. После некоторого совещания было принято решение писать ее наиболее простым способом, при этом было абсолютно не ясно, как долго будет работать выбранный алгоритм. Интуиция подсказывала, что надо попытаться. За пятнадцать минут до конца мы ее сдали и переместилось, как выяснилось позже, на седьмую строчку в мировом рейтинге. Это было достойным завершением нашей карьеры. Правила таковы, что запрещают участвовать одному человеку, если он более раза участвовал в финале.

В конце хочется написать искренние добрые слова в адрес наших постоянных и бессменных тренеров и руководителей. Вклад Натальи Львовны Андреевой и Антонины Гавриловны Федоровой в развитии всего движения олимпиад по программированию в Саратове переоценить нельзя. Результаты, достигнутые нашей командой, следствие огромной работы проделанной ими. Я не ошибусь, если скажу, что наша команда состояла из пяти человек.

И последнее, 16 мая 2003 года состоится интернет-соревнование IPSC 2003. В этот день нашей команде исполнится три года.

Современное примечание: На IPSC 2003 года мы заняли первое место. И на IPSC 2004 тоже :-)

Календарь: (c) 2011 Anatoly Rr

Проект Codeforces желает всем пользователям успехов в Новом Году. Пусть ваши хэндлы меняют цвет только в сторону красного, ваши решения не требуют дебага, а заветное «Полное решение» неоднократно радует вас каждый контест! Желаем вам в наступающем году удачи во всех делах – это же так приятно, когда удача на твоей стороне!

Традиционно Codeforces дарит возможность пользователям сменить хэндл. Обратите внимание, что сделать это можно только один раз – сменить хэндл на прежний у вас не получится. Взвесьте все за и против, ведь именно так вас часто будут называть многочисленные участники соревнований Codeforces.

Есть еще хорошие новости. Мы решили расширить список тех, кто может получить роль «тренер» в проекте Codeforces::Тренировки. Больше тренировок хороших и разных! Теперь эту роль могут получить те, кто:

• обладает красным цветом хэндла (т.е. рейтинг не менее 2200),
• или обладает оранжевым цветом хэндла, участвовал в офиц. соревновании Codeforces не более полугода назад и принял участие не менее чем в 30 рейтинговых соревнованиях Codeforces).

Это нововведение примерно вдвое расширяет список потенциальных тренеров! Нововведение будет внедрено в первой половине января.

Напоследок самое приятное! У нас появилась возможность увеличить поощрение авторам за подготовку соревнований. Мы надеемся, это немного мотивирует тех, кто мог бы сделать интересный раунд. В 2013-м году поощрение авторов составит:

• подготовка Div.1 + Div.2 раунда (руб.): 10000 + 2000^*,
• подготовка Div.2 раунда (руб.): 4000 + 2000^*.

Сумма со звездочкой – это дополнительный бонус автору «за качество». Он будет выплачиваться, если автор работал, не срывая сроки подготовки, а его раунд прошел без каких-либо заметных проблем в задачах (не было важных доп. объявлений, правок решений/тестов/чекеров/валидаторов и т.п.).

Мы надеемся на плодотворную работу с авторами в 2013-м году, надеемся, что наши лучшие участники сделают подарки сообществу в виде интересных контестов! По вопросам подготовки раунда следует писать личное сообщение координатору задач проекта — Gerald-у (Геральду Агапову).

С Новым Годом! Ура-ура!

С наступающим Новым Годом!

На часах без пары дней Новый Год – самое время подвести итоги уходящего года. Если говорить коротко, то год для проекта оказался очень продуктивным. На Codeforces были проведены крупные чемпионаты, раунды следовали один за одним, был запущен подпроект Codeforces::Тренировки, были сделаны многочисленные улучшения/исправления/нововведения. Вот короткий список наших свершений:

• учет авторитета при голосовании за комментарии/посты, fraud detection эвристики
• открытие и множественные улучшения проекта Codeforces::Тренировки
• внедрен Codeforces Markup на базе Markdown со вспомогательными тегами Codeforces
• на платформе Codeforces совместно с ВКонтакте был проведен очень масштабный чемпионат VK Cup 2012, около 6000 участников!
• на платформе Codeforces компания КРОК провела Открытый чемпионат Москвы и Московской области по программированию, около 1500 участников!
• на платформе Codeforces компания ABBYY провела чемпионат ABBYY Cup 2.0, около 2000 участников!
• внедрено прикрепление блогов к сореваниям в качестве анонсов/разборов и т.д., полуавтоматизировано прикреплены разборы прошедших контестов
• на платформе Codeforces компания Bayan провела отборочный этап Bayan Programming Contest 2012/13, более 3000 участников!
• на платформе Codeforces компания КРОК провела чемпионат КРОК по программированию среди студентов МГТУ им. Баумана, около 2000 участников!
• сделаны множественные улучшения проекта testlib.h
• поддержаны новые языки программирования
• поддержана динамическая сложность задач
• поддержана вставка фотоальбомов из Picasa в посты
• поддержаны интерактивные задачи – несмотря на короткую формулировку это очень большой пункт
• множественные улучшения проекта Polygon
• поддержаны задачи с оценкой в баллах и частичными решениями (для соревнований по типу "марафон")

И это еще не все! Хочется похвалиться веселыми картинками с приятными графиками.

Update: Выпущен новый релиз 0.8.5. Скачать новую версию вы можете с сайта проекта. Новая версия внедрена во все сервисы Codeforces и Polygon. Изначально этот пост содержал информацию о девелопмент-версии, но сейчас он используется для описания версии 0.8.5.

Библиотека testlib — самая популярная и развитая библиотека для написания чекеров, генераторов, валидаторов и теперь интеракторов для задач. Первая версия testlib.h была написана мной в 2005-ом, и представляла по большей степени порт testlib.pas на С++. С тех пор многое было улучшено и расширено. В настоящий момент она активно используется в задачах Codeforces, разных этапах Всероссийской олимпиады школьников, многих петрозаводских контестах, всех саратовских соревнованиях и т.д.

Вот основные изменения/улучшения.

Комментарий программы: stdout -> stderr

Теперь системные сообщения testlib-программ (чекеров, валидаторов, интеракторов) направляются в стандартный поток ошибок (stderr) вместо стандартного потока вывода (stdout). Это сделано для идентичности поведения при написании интеракторов, стандартный вывод которых уходит в программу участника и не может использован для вывода системных сообщений. Это может повлиять на некоторые тестирующие системы, будьте внимательны!

Интеракторы

Появилась поддержка интеракторов. Напомню, что интерактор это программа взаимодействующая с решением участника при тестировании интерактивных задач. Интерактор читает одновременно содержимое теста (первый параметр командной строки, в интеракторе — это inf), вывод программы участника (передается на стандартный ввод интерактора, в интеракторе — это ouf), выводит данные в решение участника (в интеракторе выводите в cout или используйте другой вывод, не забывайте flushes), выводит спец. файл для последующей обработки его чекером (вывод в поток tout, который похож на cout).

Пример интерактора:

#include "testlib.h"
#include <iostream>

using namespace std;

int main(int argc, char* argv[])
{
    setName("Interactor A+B");
    registerInteraction(argc, argv);
    
    // reads number of queries from test file
    int n = inf.readInt();
    for (int i = 0; i < n; i++)
    {
        // reads query from test file
        int a = inf.readInt();
        int b = inf.readInt();

        // writes query to the solution, endl makes flush
        cout << a << " " << b << endl;

        // writes output file to be verified by checker later
        tout << ouf.readInt() << endl;
    }

    // exit with message
    quitf(_ok, "%d queries processed", n);
}

readStrictReal/readStrictDouble

У потоков inf/ouf/ans появились функции readStrictReal/readStrictDouble (это одно и то же). Они очень строго читают вещественные числа, применимы в большей степени в валидаторах. Принимают аргументы:

• минимальное значение числа,
• максимальное значение числа,
• минимальное число цифр после десятичной точки (не обязательный),
• максимальное число цифр после десятичной точки (не обязательный),
• имя читаемой переменной (для вывода при ошибке).

Еще раз повторюсь — это нововведение нужно для валидаторов.

Защита от потерянных quit/quitf и readEof

Если вы пишите чекер, то легко забыть в какой-нибудь ветке выполнения сделать правильный quit или quitf. Раньше в этом случае чекер скорее всего завершался с exitcode 0 и для участника это означало вердикт "правильный ответ на тест". Теперь testlib автоматически при выходе проверит что был в самом деле вызван quit/quitf (это работает для чекеров) и аварийно завершит работу, если вызова не было. Аналогично, если валидатор не сделал чтение конца файла (readEof), то произойдет аварийное завершение.

quitif

В чекерах (и не только) очень популярна конструкция вида:

if (answer != output)
    quitf(_wa, "Expected %d, found %d", answer, output);

Теперь ее можно записать чуть короче, используя функцию "выйти если" (quitif): quitif(answer != output, _wa, "Expected %d, found %d", answer, output);

Улучшение производительности

Вместо слов короткий пример. Запускаем простой чекер сравнения миллиона целых чисел (вывод и ответ ~ 7.5 мегабайт, для C++ использовался g++ 4.6.1, а для pascal — Delphi 7):

• предыдущий релиз testlib.h — 2.8 секунды,
• паскалевский testlib от ИТМО — 3 секунды,
• паскалевский testlib от СПбГУ — 4 секунды,
• новая версия testlib.h — 0.35 секунды

Таким образом, можно утверждать, что мнение о медленной работе предыдущих версий — просто миф, а новый testlib быстрее предыдущего примерно в 8 раз!

Аналогичные измерения, если использовать текстовые чекеры (сравнения строк или токенов):

• предыдущий релиз testlib.h — 1.2 секунды,
• паскалевский testlib от ИТМО — 3.5 секунды,
• паскалевский testlib от СПбГУ — 2 секунды,
• новая версия testlib.h — 0.25 секунды.

Миф подтверждается, а время работы сократилось вдвое. Видимо, на больших файлах скорость работы возросла примерно в 3-6 раз.

Функции-помощники

Добавлены несколько простых полезных функций (некоторые уже были):

• lowerCase(std::string), upperCase(std::string) — перевести строку в нижний или верхний регистр,
• trim(std::string) — удаляет слева и справа строки пробелы, табы и символы перевода строк,
• vtos(T) — шаблонная функция, превращает экземпляр T в строку (медленная, использует stringstream),
• format(шаблон, параметры), например format("n=%d", 5) — возвращает строку по шаблону и параметрам,
• englishEnding(int) — правильное окончание для числительного, например englishEnding(2)="nd",
• compress(std::string) — заменяет длинную строку более короткой, оставляя ее префикс и суффикс, а между ними многоточие, очень полезна при выводе в комментарий какого-либо вывода участника,
• startTest(int) — используется в мультигенераторах, фактически делает freopen(имя-тест, "r", "stdin"), то последующий вывод перенаправляется в файл с именем равным номеру теста.

Мелочи

Макросы I64, U64

Теперь определены макросы:

#ifdef ON_WINDOWS
#define I64 "%I64d"
#define U64 "%I64u"
#else
#define I64 "%lld"
#define U64 "%llu"
#endif

Пример использования: printf("n=" I64 ", m=%d", n, m). Используйте их для ввода-вывода 64-битных знаковых/беззнаковых чисел через scanf/printf. Хотя такое делать почти не надо, так как чтение происходит через inf/ouf/ans, а при выводе лучше сделать vtos(n).

Случайный элемент коллекции (отрезка итераторов).

Теперь можно в генераторе написать так: cout << rnd.any(v) << endl, где v — это вектор. Так же поддерживается вариант с парой итераторов random_t::any(begin, end), т.е. произвольный элемент массива можно получить так rnd.any(a, a + n).

Issue

Исправлен issue с пространством имен около iter_swap, из за чего были проблемы с компиляцией на некоторых GCC g++.

Новый члены-функции у InStream: readWordTo/readTokenTo/readStringTo/readLineTo

Такие функции были добавлены для ускорения чтения в чекерах (валидаторах и т.д.), где приходится очень много читать. Например, вот так может выглядеть основной код чекера, который сравнивает ответы и вывод по словам (токенам):

    string j, p;
    while (!ans.seekEof() && !ouf.seekEof()) 
    {
        n++;
        ans.readWordTo(j);
        ouf.readWordTo(p);
        if (j != p)
            quitf(_wa, "%d%s words differ - expected: '%s', found: '%s'", n, englishEnding(n).c_str(), compress(j).c_str(), compress(p).c_str());
    }

InStream::quitf

Добавлен InStream::quitf, теперь. Помните, что для потоков ans/inf любая причина выхода, отличная от _fail приводит к _fail. Например, следующий участок кода корректен

int readAnswer(InStream& in)
{
    int n = in.readInt();
    if (n % 2 != 0)
        in.quitf(_wa, "n should be even, but %d found", n);
    return n;
}

int main(int argc, char * argv[])
{
    registerTestlibCmd(argc, argv);
    
    int ja = readAnswer(ans);
    int pa = readAnswer(ouf);
    
    quitif(ja > pa,
        _fail, "expected %d, found %d", ja, pa);
    quitif(ja < pa,
        _wa, "expected %d, found %d", ja, pa);
    
    quitf(_ok, "answer is %d", ja);
}

Если выведено нечетное число в файл с ответом, то будет _fail, а если в вывод участника — то _wa.

Стандартные чекеры/валидаторы

В стандартные поставляемые чекеры были добавлены два чекера: caseicmp.cpp и casencmp.cpp, которые работают в случае стандартной для ACM-ICPC Finals разметки multitestcase. Первый из них поможет, если надо проверять одно целое число на testcase, а второй — если последовательность чисел.

Тестирование

Новый код усиленно тестировался, в частности в полуавтоматическом режиме на большом количестве тестов. Сравнивалось, что stdout/stderr и exitcode чекера не изменился после его компиляции с новым testlib.h.

2-го декабря состоится очередной (17-й) полуфинал Чемпионата Мира — Northeastern European Regional Contest 2012!

Желаем удачи командам, а болельщикам — побольше радостных моментов!

Полезные ссылки:

• таблица результатов
• блог Петра Митричева
• онлайн-трансляция награждения

До полуфинала NEERC 2012 осталось совсем чуть-чуть, а до финального этапа ВКОШП 2012 — пара дней. Желаю не тупить и не бажить, поменьше дебага и побольше Accepted-ов!

Перед столь важными соревнованиями всегда полезно вспомнить свои удачные выступления, а порой даже просто чудесные случаи. Верьте в чудеса!

Предлагаю тему — давайте вспомним чудеса на контестах, которые случались с вами. Лично я всегда упоминаю такой случай.

Посмотрите на этот ранклист (Петрозаводск, зима 2003):

Final Contest, Saturday, February 08, 2003                              RESULTS
 ID  Team                            A   B   C   D   E   F   G   H    = Time  R
-------------------------------------------------------------------------------
 05  Saratov SU#3                    .   +9  +12 .   .   .   .   +    3 1045  1
 09  Outsiders                       .   +2  +   .   .   .   .   .    2  253  2
 19  Trinity                         .   +   .   .   -5  .   .   +    2  282  3
 07  SPb IFMO 2                      .   +2  -3  .   -4  .   .   +    2  378  4
 01  SPb IFMO 1                      .   +1  .   .   -3  -2  .   .    1  104  5
 16  DNK                             .   -4  .   .   .   .   .   +    1  241  6
 18  Noname                          .   -7  .   .   .   .   .   +    1  268  7
 06  SPb SU#3                        .   -8  .   +2  .   .   .   .    1  318  8
 20  SPb ETU 1                       .   -3  .   .   .   .   .   +3   1  327  9
 02  SPb SU 24                       .   -2  .   .   .   .   .   .    0    0 10
 03  New                             .   -1  -7  .   .   .   .   .    0    0 10
 04  YaRiK                           .   -7  .   .   .   .   .   .    0    0 10
 08  MSU SA                          .   .   .   .   .   .   .   .    0    0 10
 10  ME4TA                           .   .   .   -3  .   .   .   .    0    0 10
 11  Antivirus                       .   .   .   .   .   .   .   .    0    0 10
 12  Jupiter                         .   .   .   .   .   .   .   -22  0    0 10
 13  HACMOPK                         .   .   .   .   .   .   .   .    0    0 10
 14  BM                              .   .   -11 .   .   .   .   .    0    0 10
 15  AI                              .   .   .   .   .   .   .   .    0    0 10
 17  Wx4                             .   .   -4  .   .   .   .   .    0    0 10

Команда Saratov SU 3 — это мы: Эльтерман, Лазарев, Мирзаянов. Последняя попытка в этом контесте — наша. За 16 секунд до окончания мы получили ACCEPTED по задаче С. Особый смак добавляет факт, что решали ее в основном Андрей Лазарев и я. Мы написали по тем временам сложное решение со случаями и КМП, оно падало с WA на каких-то тестах, и под конец соревнования у нас совсем опустились руки. Волевым решением на последних минутах капитан команды Илья Эльтерман попросил нас от клавиатуры и (почти не зная задачу!) стал делать попытку за попыткой делая случайные изменения кода. В ход пошли замены < на <= (и наоборот), всякие +1 и -1 в формулах и прочие сомнительные изменения.

Он сделал несколько попыток, приходили разные вердикты WA, PE и так далее. Контест закончился, мы расстроенные пошли на обед. Я же решил успеть написать письмо до обеда и минуты через две после окончания контеста, закрыв MessageBox, понял, что там было написано <<ACCEPTED!>>.

Да-да, именно так мы победили на тех сборах :-) Верьте в чудеса!

А о каких чудесах можете рассказать вы?

NCPC (Nordic Collegiate Programming Contest) — регулярное соревнование по программированию среди студенческих команд северных стран Европа. Проводится удаленно в большом количестве университетов. Организован в основном силами нескольких вузов Швеции. Имеет статус, близкий к российским четвертьфиналам в чемпионате ACM-ICPC.

Материалы NCPC традиционно публикуются, за что отдельное спасибо организаторам.

Контест этого года доступен в Codeforces::Тренировках: 2012 Nordic Collegiate Programming Contest (NCPC)

Этот контест — отличная тренировка перед четверть- или полуфиналом!

Прошла вторая командная олимпиада из цикла интернет-олимпиад, проводимых ИТМО. Олимпиада проходила в двух секциях — базовой и усложненной. Задачи в секциях довольно сильно пересекались.

Некоторое обсуждение прошедшей олимпиады здесь.

В Codeforces::Тренировки были добавлены:

• 2012-2013 Цикл интернет-олимпиад. Вторая командная олимпиада (20 октября 2012). Базовый уровень.
• 2012-2013 Цикл интернет-олимпиад. Вторая командная олимпиада (20 октября 2012). Усложненный уровень.

Вы можете как решать эти контесты виртуально (если вы раньше не видели задачи), так и просто дорешивать их.

Прям сейчас начался четвертьфинал в Саратове. Болеть можно по ссылке результаты.

В понедельник можно будет принять участие в зеркале на http://acm.sgu.ru/. Время начала зеркала 22 октября (понедельник), 2012, 16:00. В ранклист зеркала будут интегрированы результаты официальных участников. Позже появится тренировка и на Codeforces.

Из особенностей нашего четвертьфинала хочется упомянуть:

• CodeGame Challenge,
• участники сами выбирают писать под Windows или Linux — да, тестируем тоже в двух режимах,
• набор задач, интересный разным по уровню командам,
• в этом году поддержали интерактивные задачи — есть такая в проблемсете.

Надеюсь, что участникам понравится контест!

Всем привет.

Недавно на NEERC Trains прошла первая третья командная тренировка. Кстати, победил на этой тренировке интригующий состав "SPb NRU ITMO 1: Kever, Korotkevich, Nigmatullin" :-) На тренировке использовался контест Варшавы со старых петрозаводских сборов.

В тренировки добавлена тренировка 2007-2008 Зимние Петрозаводские сборы, Контест Варшавского университета. Среди призраков-участников вы найдете не только участников Петрозаводских сборов 2008-го года, но и текущие составы ИТМО!

Приятной подготовки к четвертьфиналам!

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