Добрый день, Codeforces!
Сегодня я расскажу вам о новой функции системы Polygon, в которой готовятся все задачи для раундов Codeforces. Конечно, система открыта для любых пользователей — в ней подготавливается большое количество контестов для других соревнований или сборов.
Двумя ключевыми элементами задачи, помимо авторского решения, тестов и условия, являются две программы: валидатор и чекер.
Валидатор (англ. Validator) — это программа, которая считывает тест и сообщает, соответствует ли он условию задачи или нет. Валидаторы необходимо писать абсолютно формально — валидатор пропускает тест тогда и только тогда, когда он соответствует условию задачи и может быть спокойно добавлен в набор тестов. Валидаторы удобно писать с помощью библиотеки testlib.h. Иногда авторы пренебрегают валидаторами (на соревнованиях Codeforces такого не случается), что ставит под угрозу корректность тестов. Так как в соревнованиях Codeforces присутствуют взломы, важность правильности валидатора значительно возрастает. Естественно, все взломы перед тем, как попасть к решению участника, проходят валидацию. В большинстве задач валидаторы относительно простые, но когда в задаче появляются дополнительные условия (например, что решение для теста существует), то сложность валидатора значительно возрастает.
Чекер (англ. Checker) — это программа, которая на вход получает тест, вывод программы участника и вывод программы жюри и определяет правильность вывода участника. К сожалению, ошибки в чекерах часто приводят к тяжелым последствиям. Далеко не во всех задачах можно просто сравнить ответы на равенство. Например, в задаче 234H - Слияние двух колод в чекере используется декартово дерево. Если по условию задачи требуется сертификат, то чекер лучше всего писать в концепции readAnswer(ans)/readAnswer(ouf). Это концепция и многое другое по теме разработки чекеров описано в древнем посте Чекеры, testlib.h и просто по теме. Чекеры удобно писать с помощью библиотеки testlib.h.
Тестирование этих программ обычно происходит либо вручную из командной строки, либо косвенно — добавлением неправильных решений и временным добавлением невалидных тестов. На практике авторы часто пренебрегают внимательным тестированием валидаторов и чекеров. В самом деле такая методика тестирования неудобна, а тесты не сохраняются. При совместной работе соавтор не сможет просмотреть тесты, на которых тестировались валидатор/чекер, или перезапустить их после внесения исправлений в валидатор или чекер.
В обновленной версии Polygon всё стало значительно лучще! Мы сделали удобные средства для тестирования валидатора и чекера.
Добрый вечер, друзья!
За обсуждением животрепещущей темы использования чужого кода в своих решениях можно и не заметить, что приближается зима 188 раунд платформы Codeforces!
А ведь мы постарались подготовить для вас набор задач с любопытными (и, как нам хочется думать, не сильно сложными) идеями и понятными условиями.
Мы — это авторы задач yaro и Rei, куратор раундов Codeforces Gerald и автор системы mikemirzayanov. Отдельное спасибо Паше (pavelkunyavskiy) и Артему (RAD) за тестирование и дельные замечания.
Последний раз, когда я участвовал в проведении соревнования на Codeforces, раунды еще носили статус "beta". Но чем меньше "beta", тем больше ответственность. В связи с этим желаю организаторам и авторам еще одного успешно проведенного раунда. Участникам же — нестандартных задач и идей, чистого кода (а также чистой клавиатуры) и побольше правильно сданных решений!
Нам представляется непростой задачей оценить уровень сложности задач для всей массы участников, поэтому разбалловка будет динамическая. Все же ради любопытства сделаем следующее предположение об относительной сложности задач: div.1: B-B-C-C-E, div.2: A-B-C-C-E. Угадаем ли?
UPD Приносим извинения за проблемы с очередью тестирования Codeforces.
В любом случае, нам будет очень приятно, если вы оцените наш раунд (после его завершения): short survey.
В упорной борьбе с отрывом в один взлом победителем div.1 стал meret (Jakub Pachocki)!
Доступны результаты первого дивизиона, результаты второго дивизиона.
Друзья, вот и закончился онлайн-тур ABBYY Cup 3.0!
Спасибо большое всем участникам! Мы приносим свои извинения за проблемы с тестированием. MikeMirzayanov всех уже обрадовал планами о закупке тестирующих машин. Надеемся, что в будущем таких ситуаций не повторится.
А вот и разборы задач:
Это была одна из самых простых задач из предложенных. Решение задачи сводится к рассмотрению нескольких случаев. Изначально ответ равен единице. Заметим, что если в строке встречается "?", то он увеличивает число возможных кодов в 10 раз. За исключением случая, когда "?" стоит в начале строки. Тогда он увеличивает число возможных кодов в 9 раз. Далее нужно рассмотреть случаи, когда среди символов строки встречаются буквы. Тут нужно рассмотреть два случая:
Заметим, что в данной задаче необязательно реализовывать длинную арифметику. Так как все операции за исключением умножения на 10 из-за "?" можно выполнять с помощью стандартной арифметики. А для умножения на 10 можно просто вывести в ответ нужное количество нулей.
Заметим, что понятие порядка мячей соответствует перестановке, а ограничение на число бросков для ученика соответствует ограничению на число транспозиций. Нужно посчитать число “подходящих” перестановок. Заметим, что если перестановку разбить на циклы, и в каждом цикле будет не более двух элементов с максимальным числом инверсий равным 1, то рассматриваемая перестановка является “подходящей”. Таким образом, задачу можно решить с помощью динамического программирования. Нужно вычислять функцию f(a, b), где a – число 1, а b – число 2, которые мы использовали. f(a, b) – число “подходящих” перестановок. Заметим, что данную функцию можно вычислять с помощью следующей формулы: 
, где I(n) = I(n - 1) + (n - 1) * I(n - 2)) Ее доказательство оставляем читателям в качестве упражнения.
Данная задача имеет множество решений. Рассмотри одно из них. Обозначим исходное изображение за T. Будем применять к T две операции: эрозия и дилатация. Операция эрозии – замена всех пикселей, которые относятся к изображению и граничат с пикселями фона, на пиксели фона. Дилатация – это в некотором смысле обратная операция, мы заменяем пиксели фона, которые граничат с пикселями изображения, на пиксели изображения. Заметим, что для определения соседних пикселей лучше использовать 4-связность. Итак, мы применяем к исходному изображению несколько операций эрозии. После этого лучи исчезнут и останутся только центры солнышек. Далее применяем несколько операций дилатации. Заметим, что число операций дилатации должно быть больше, чем операций эрозии. Обозначим полученное изображение за P. Далее рассматриваем исходное изображение T и выделяем в нем компоненты связности, соответствующие солнышкам. Далее из каждой такой компоненты необходимо выделить части, соответствующие лучикам. Лучикам соответствуют, в свою очередь, Пиксели изображения, которые есть на изображении T, и которых нет на изображении $P.
Первое, что нужно сделать в данной задаче – это выделить цепочки в заданной очереди. Цепочка – это последовательность бобров, которые стоят в очереди непосредственно друг за другом. Таким образом, мы получим все длины цепочек и цепочку с Умным Бобром. И далее требуется просто применить стандартное ДП для вычисления возможных сумм.
Перейдем от исходной матрицы к двухдольному графу. Элементы матрицы (i, j) с четными значениями i + j поместим в одну долю, а с нечетными — в другую. Ребра будут соответствовать квадратам, которые находятся рядом. Далее добавим веса для ребер. Ребра, соединяющие одинаковые элементы матрицы, будут иметь вес 0, соединяющие разные — вес 1. После этого в полученном графе нужно будет найти максимальное паросочетание минимального веса. Его вес будет ответом к задаче. Обоснование вышеизложенного заключается в том, что любой ответ для задачи будет представлять собой некоторое разбиение исходной матрицы на пары. Заметим, что для некоторого разбиения минимальное число элементов матрицы, которые изменятся, будет соответствовать числу пар, в которых числа различаются. Таким образом, оптимальным будет то разбиение на пары, в котором число пар одинаковых элементов будет максимальным. Заметим также, что для построения максимального потока минимальной стоимости требовалось использовать какой-нибудь эффективный алгоритм. Например, можно было использовать алгоритм Дейкстры с кучей вместе с преобразованием весов ребер алгоритма Джонсона.
Для решения данной задачи будем использовать дерево отрезков. Рассмотрим некоторый отрезок [l;r] на этом дереве. Для него введем функцию S(x), где x – целое число. S(x) = F0 + xAl + F1 + xAl + 1 + … + Fr - l + xAr, где Fi – i-е число Фибоначчи, Ai – рассматриваемый массив целых чисел. Заметим, что S(x), для x = 0, 1, 2…, представляет собой некий аналог чисел Фибоначчи. То есть S(x) = S(x - 1) + S(x - 2), для x≥2. Из этого следует, что нам для каждого отрезка [l;r] нужно хранить только S(0) и S(1). А для вычисления S(x) для x≥2можно пользоваться следующей формулой: S(x) = S(0)Fx - 2 + S(1) * Fx - 1. Итого, разрешение запросов 2-го типа сводится к вычислению не более чем 
значений S(x) для различных отрезков. Модификации 1-го типа выполняются тривиальным проходом по дереву. Для запросов 3-го типа нужно использовать дополнительную информацию в дереве и частичные суммы чисел Фибоначчи.
Для начала нужно научиться быстро сравнивать две любые подстроки, которые можно взять из исходной строки или из одной из строк, соответствующей правилам. Это можно сделать, например, с помощью построения суффиксного массива, содержащего все строки ввода. После построения такого массива и вычисления значений LCP задача сравнения двух подстрок сводится к вычислению числа одинаковых символов и сравнении символов, которые идут после одинаковых блоков. Вычисление числа одинаковых символов эквивалентно задаче вычисления минимума на интервале массива значений LCP. Так как массив LCP не меняется, то эффективное разрешение таких запросов можно делать с помощью RMQ-алгоритмов. Таким образом, мы можем за O(1) сравнивать две любые подстроки. Заметим, что время препроцесса зависит от используемых алгоритмов для построения суффиксного массива и построения RMQ.
Далее нам нужно научиться находить число вхождений некоторой подстроки исходной строки в строку одного из правил. Это можно делать с помощью бинарного поиска по суффиксному массиву строки правила. Заметим, что мы можем сравнивать две подстроки за время O(1). Поэтому сложность поиска числа вхождений подстроки в строку будет 
. Теперь рассмотрим некоторый суффикс исходной строки. Мы знаем его LCP с предыдущим суффиксом. Это будет нижняя граница на длину этого суффикса. Заметим, что число вхождений некоторого префикса рассматриваемого суффикса монотонно зависит от длины этого префикса. Поэтому, для каждого правила можно бинарным поиском определить, какой может быть минимальная и максимальная длина префикса, чтобы он подходил под правило. После чего необходимо просто пересечь все полученные интервалы.
Возможно, что с использованием других структур данных на строках можно получить более простое решение. Техническая реализация рассматриваемого решения является довольно трудоемкой.
Разбор задач ABBYY Cup 3.0
UPD2: Дорогие участники!
Как мы и обещали, лучших 25 участников по результатам онлайн-тура ABBYY Cup 3.0 и победителей конкурса задач мы приглашаем на День открытых дверей ABBYY, который состоится 17 июля в московском офисе ABBYY. Всем гражданам РФ мы предоставим полную компенсацию дороги туда-обратно (по предварительному согласованию суммы), с остальными победителями вопрос компенсации будет обсуждаться индивидуально.
Дорогие победители, напишите, пожалуйста, в течение 5 дней нам на электронный ящик abbyycup@abbyy.com о своем желании приехать.
Если вы не попали в 25 лучших и не являетесь победителем конкурса задач, но очень хотите приехать, также напишите нам в эти сроки. Напоминаем, что всех участникам Дня открытых дверей мы обеспечим питанием и проживанием.
По нашему опыту, примерно треть участников Дней открытых дверей состоит из ребят, не прошедших в финал. Мы считаем очень важным поддерживать менее опытных спортивных программистов, которые не посещают из года в год столичные онсайты, и дать им возможность познакомиться с IT-индустрией, пообщаться с коллегами в неформальной обстановке.
UPD1: Разборы!
UPD: Друзья, уже сегодня состоится онлайн-тур ABBYY Cup 3.0!
На всякий случай, несколько замечаний:
Приятного всем контеста!
Всем привет!
Мы рады анонсировать долгожданный ABBYY Cup 3.0! Как и обещали, в этом году участники будут решать самые интересные задачи, присланные на апрельский конкурс задач. ABBYY Cup 3.0 будет состоять из двух частей: онлайн и онсайт. Первая часть пройдет уже совсем скоро, в среду 12 июня с 17:00 до 21:00.
Мы благодарим проект Codeforces, особенно MikeMirzayanov и Gerald за помощь в проведении соревнований. Также спасибо большое всем участникам конкурса задач по спортивному программированию! Дорогие победители конкурса, не удивляйтесь, если не узнаете своей задачи. Во-первых, она могла попасть на онсайт. Во-вторых, ее могли сильно модифицировать.
Подробности
В онлайн-туре будет 6 задач, каждая стоимостью в 100 баллов. Задачи разбиты на тесты двумя способами: либо на две группы (легкую и сложную) стоимостью в 30 и 70 баллов соответственно, либо на три (легкую, среднюю и сложную) стоимостью в 30, 40 и 30 баллов соответственно. Также вас ждет "теплая" эвристическая задача, которая не оставит никого равнодушным!
Официальные языки соревнования – C/C++, Pascal, C# и Java. Задачи можно сдавать на всех языках, поддерживаемых на Codeforces, но жюри не гарантирует существования полных решений на всех языках из этого списка. Засчитывается только полное прохождение группы тестов. При равенстве баллов штрафное время учитывается по правилам ACM. Полное решение какой-либо группы тестов засчитывается за сданную ACM-задачу, и в соответствии с этим вы будете получать штрафное время. Отметим, что в этом году ABBYY Cup является рейтинговым для всех участников (школьники, студенты, выпускники и т.д.). Регистрация на ABBYY Cup 3.0 откроется за 12 часов до соревнований и закроется с окончанием контеста. Напоминаем, что победители конкурса задач могут участвовать в соревновании только вне рейтинга.
А что потом?
По итогам онлайн-тура 25 лучших пройдут в финал, который состоится 17 июля в московском офисе ABBYY в рамках Дня открытых дверей ABBYY. Все участники контеста, независимо от результата, имеют возможность приехать на День открытых дверей ABBYY! Компенсация дороги будут обговариваться с каждым индивидуально, проживание и питание будут предоставляться за счет компании. Напоминаем, что победители конкурса задач уже приглашены на День открытых дверей. Мы предполагаем, что всего мы пригласим не более 50 человек. Если вы не попадете в 25 лучших, не являетесь победителем конкурса задач и никогда не были у нас на Дне открытых дверей, но хотите приехать, напишите нам о своем желании на abbyycup@abbyy.com в течение 5 дней после контеста. Мы обязательно постараемся вас пригласить. Что такое День открытых дверей ABBYY и как он проходил в 2011 г. и в 2012 г. в блоге I_love_ilona.
Как всегда, результаты ABBYY Cup могут быть зачтены как первый этап собеседования при трудоустройстве в ABBYY или при поступлении в магистратуру ABBYY в МФТИ.
Анонс ABBYY Cup 3.0
Всем привет!
Я надеюсь, никто не забыл, что каждый год перед ICPC World Finals проводится небольшое соревнование ICPC Challenge. Разумеется, этот год не будет исключением. Если вдруг кто-то не знает об этом, то ICPC Challenge — это дополнительный двухнедельный контест по программированию искусственного интеллекта в какой-нибудь игре для финалистов чемпионата мира по программированию ACM-ICPC. Победитель определяется по системе double-elimination tournament, и будет объявлен на одном из мероприятий Финала.
ICPC Challenge 2013 начался несколько дней назад (точнее 3 июня), и сейчас я хочу торжественно объявить, что он был подготовлен небольшой командой из Baylor University, North Carolina State University и Saratov State University, который я представляю! Мы приготовили для вас новое задание, которое носит название CodeRunner.
Немного об игре
Задание на 2013 ICPC Challenge, CodeRunner, представляет собой игру на прямоугольном поле, которое выглядит как на картинке ниже. Красный и синий игроки перемещаются по полю, собирают золото, убегают от врагов, которые двигаются по полю. Каждый игрок может перемещаться вбок, карабкаться вверх и спускаться вниз по лестницам, а кроме того разбивать кирпичи, которые находятся на игровом поле. Кирпичи могу восстанавливаться через некоторое время после разрушения.
Приятная новость
Но самая главная новость заключается в том, что в этом году в соревновании могут участвовать все желающие! Параллельно с основным ICPC Challenge для финалистов чемпионата мира, мы запускаем новое соревнование Open ICPC Challenge. Каждый может принять в нем участие и сразиться против лучших команд по программированию в игре CodeRunner!
Вы можете найти больше информации тут и тут.
Мы будем рады видеть каждого из вас :)
Удачи!
Всем привет!
Совсем скоро, 7 июня в 19:30 MSK состоится Codeforces Round #187, автором которого являюсь я. Это мой седьмой раунд на Codeforces и я надеюсь, что не последний.
Спасибо Геральду Агапову (Gerald), Роману Фурко(Furko) и Аксенову Виталику(Aksenov239) за помощь в подготовке раунда и Марии Беловой (delinur) за перевод условий на английский.
Настоятельно рекомендую прочитать условия ВСЕХ задач.
Gl & hf ! :)
Наше сообщество продолжает расти и развиваться! Мы рады сообщить, что недавно зарегистрировался стотысячный пользователь Codeforces. Спасибо всем, кто помогает двигать вперед проект — авторам задач, тестерам, партнерам и, конечно, всем членам сообщества. Отдельные слова благодарности компании ВКонтакте!
Приятной статистики не бывает много. Вот еще немного цифр:
- наша база данных содержит более 3,5 миллионов отосланных вами решений,
- количество задач приближается к 3000,
- количество посетителей сайта в месяц превосходит 400000,
- количество просмотров страниц в месяц составляет примерно 5000000.
Общая информация
Саратовский государственный университет в первой половине августа проводит международную летнюю студенческую школу по программированию. Продолжительность школы — десять дней, школа пройдет с 5-го по 15-е августа.
К участию приглашаются как команды из двух-трех человек, так и индивидуальные участники.
Школа пройдет в живописном месте, на одной из саратовских баз отдыха на берегу Волги. Участники будут расселены в уютных номерах по 2-4 человека и обеспечены трехразовым питанием. На территории базы имеется собственный пляж и спортивные площадки.
В программе школы запланировано 10 рабочих дней, включающих ежедневные пятичасовые тренировки, разборы задач, дорешивания. Будет прочитана серия лекций. Учебная программа рассчитана на студентов младших и средних курсов, которые хотят достичь значительных успехов на соревнованиях по программированию.
Всем привет!
В ближайший четверг 30 мая в 19:30 MSK пройдет Codeforces Round #186 (Div. 2), автором которого являюсь я. Это мой первый раунд на Codeforces и я надеюсь что все получат удовольствие от решения задач на нём.
Спасибо Геральду Агапову (Gerald) за огромную помощь в подготовке раунда и Марии Беловой (Delinur) за перевод условий на английский. Также, хочется поблагодарить Ваню Здомского (ballon), за то что он протестировал раунд.
Разбалловка сегодня такая: 500-1000-1500-2500-2500
Good luck & have fun! :)
Всем привет!
Раунд Codeforces Round #185 состоится в Воскресенье, 26 Мая, в 19:30 по московскому времени (23:30 по ЦПВ).
Организатор раунда — Zanoes, а задачи готовили:
- Div.1E и Div.2B —— Zanoes (Жанг Гаощанг),
- Div.1D и Div.1A —— liouzhou_101 (Ванг Квишенг),
- Div.1C, Div.1B, Div.2A —— lydrainbowcat (Ли Юдонг)
Тестеры — roosephu(Луо Юпинг), FredaShi (Ши Хаойе), sjynoi(Сун Джяю), sevenkplus(Гу Южу), xiaodao(Танг Фейху) и Riatre.
Выражаем особую благодарность Gerald за помощь в подготовке раунда, MikeMirzayanov за классную платформу и Delinur за перевод.
Распределение баллов будет стандартное, 500-1000-1500-2000-2500 в обоих дивизионах. Наверное, эти задачи проще задач из предыдущих китайских раундов :)
Это наш первый раунд на Codeforces, надеюсь, он вам понравится. Высоких вам рейтингов и удачи!
UPD: Мы очень сожалеем о нашей ошибке. Следующие слова были сказаны автором задачи div1A (div2C) liouzhou_101. http://codeforces.com/blog/entry/7773#comment-134702 .
Конечно, это также моя ошибка и ошибка Zanoes, что мы не прочитали этот чекер аккуратно и тем самым доставили проблемы Codeforces. Я приношу свои извинения за liouzhou_101, он очень старался сделать хороший контест во время подготовки раунда.
UPD2: Раунд считается не рейтинговым.