Codeforces Round #190
Автор cgy4ever, 11 лет назад, перевод, По-русски

Привет всем!

Не хотите ли Вы потренироваться перед предстоящим контестом ACM/ICPC Finals?

Codeforces Round #190 пройдет в пятницу, 28-го июня, в 19:30 MSK. Это последний шанс потренироваться перед финалом, не упустите его!

Я cgy4ever из Китая, и это мой первый раунд Codeforces. Я надеюсь, он понравится вам.

Как обычно, будет 7 задач: 2 для Div2, 2 для Div1 и 3 для обоих дивизионов. Я готовил эти задачи. Хотелось бы поблагодарить Gerald и sdya за тестирование задач, и MikeMirzayanov за проект Codeforces и Polygon.

Удачи и фана вам на раунде!

Update 1: The score distribution for Both Division is regular (500-1000-1500-2000-2500). The main character of all problem will be: Fox Ciel. (See here for more info)

Update 2: Also thanks Aksenov239 for helping prepared this round, including translate the problem statement into Russian. And I'm sorry for the delay of judgement at the beginning of this round. Fortunately it goes better now.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +347
  • Проголосовать: не нравится

Яндекс.Алгоритм 2013: тестовый раунд
Автор lperovskaya, 11 лет назад, По-русски

Мы хотели бы подробнее рассказать вам о финале чемпионата, который состоится 21–23 августа в Санкт-Петербурге. Заключительный раунд Алгоритма пройдет в необычном для IT-мероприятий месте — во дворце великого князя Владимира Александровича, построенном в 1870 году.

В финале лучшие участники чемпионата останутся один на один с тестирующей системой. Никакого интернета или заготовленного кода — только «чистая» машина и выбранная среда разработки. За их борьбой можно будет следить посредством текстовой трансляции.

Не откладывайте в долгий ящик регистрацию: тестовый раунд начнется уже завтра.

Ещё одна хорошая новость: мы решили почти удвоить количество сувенирных футболок. Теперь майку с символикой Яндекс.Алгоритма получат 75 лучших участников отборочного этапа и ещё 75 человек, выбранных случайным образом — из тех, кто решил хотя бы одну задачу. И, разумеется, все финалисты.

UPD: Тестовый раунд доступен для участников: http://algorithm.contest.yandex.ru/contest/306.

Зрители смогут следить за развитием событий, перейдя по ссылке http://algorithm.contest.yandex.ru/contest/306/standings.

UPD2 Результаты тестового раунда доступны на сайте соревнований

Полный текст и комментарии »

  • Проголосовать: нравится
  • +118
  • Проголосовать: не нравится

Codeforces Round #189
Автор havaliza, 11 лет назад, перевод, По-русски

Привет, Codeforces! :-{D

По случаю двух важных событий в мире спортивного программирования (IOI и ACM ICPC) я и мои друзья (команда Ирана на IOI) решили сделать подарок всем пользователям Codeforces, которые будут участвовать хотя бы в одном из этих двух соревнования, а также всем остальным. :)

Этот раунд подготовил я (havaliza), dani1373 и keivan, также нам помогал fab. Я хочу поблагодарить всю команду Codeforces за их усилия в поддержании этого веб-сайта.

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

Update 1. Распределение баллов по задачам в Div. 1: 500-1000-1500-2500-2500, в Div. 2 распределение стандартное.

Update 2. Большое спасибо пользователю Aksenov239, который очень много помогал нам в подготовке раунда.

Update 3. Here is the editorial. To be completed soon :)

Полный текст и комментарии »

  • Проголосовать: нравится
  • +304
  • Проголосовать: не нравится

Анонс MemSQL start[c]up
Автор AlexSkidanov, 11 лет назад, перевод, По-русски

MemSQL с радостью сообщает о проведении start[c]up -- соревнования по программированию, проводимого на Codeforces. Start[c]up состоит из двух раундов.

Оба раунда подготовлены программистами MemSQL: pieguy, nika, exod40, SkidanovAlex и dolphinigle.

Раунд 1 состоится онлайн 13 июля и будет проведен по стандартным правилам Codeforces. На нем будет представлено пять задач, сложность которых сопоставима со средним раундом на Codeforces. Для участия в первом раунде допускаются все желающие.

Раунд 2 состоится одновременно онлайн и онсайт 3 августа и будет проведен по стандартным правилам Codeforces. Будет представлено пять задач, сложность которых, по нашей оценке, превосходит средний раунд на Codeforces. Во втором раунде могут участвовать только участники, занявшие первые 500 мест в первом раунде. Лучшие 100 участников второго раунда получат футболки start[c]up.

Для тех из вас, кто находится географически в Кремниевой Долине, мы пригласим 25 лучших участников по итогам первого раунда на онсайт версию второго раунда. Победитель онсайт раунда получит специальный приз.

Больше информации о нас под катом

Полный текст и комментарии »

  • Проголосовать: нравится
  • +304
  • Проголосовать: не нравится

Новая функциональность Polygon: тестирование чекеров и валидаторов
Автор Fefer_Ivan, 11 лет назад, По-русски

Добрый день, Codeforces!

Сегодня я расскажу вам о новой функции системы Polygon, в которой готовятся все задачи для раундов Codeforces. Конечно, система открыта для любых пользователей — в ней подготавливается большое количество контестов для других соревнований или сборов.

Двумя ключевыми элементами задачи, помимо авторского решения, тестов и условия, являются две программы: валидатор и чекер.

Валидатор (англ. Validator) — это программа, которая считывает тест и сообщает, соответствует ли он условию задачи или нет. Валидаторы необходимо писать абсолютно формально — валидатор пропускает тест тогда и только тогда, когда он соответствует условию задачи и может быть спокойно добавлен в набор тестов. Валидаторы удобно писать с помощью библиотеки testlib.h. Иногда авторы пренебрегают валидаторами (на соревнованиях Codeforces такого не случается), что ставит под угрозу корректность тестов. Так как в соревнованиях Codeforces присутствуют взломы, важность правильности валидатора значительно возрастает. Естественно, все взломы перед тем, как попасть к решению участника, проходят валидацию. В большинстве задач валидаторы относительно простые, но когда в задаче появляются дополнительные условия (например, что решение для теста существует), то сложность валидатора значительно возрастает.

Чекер (англ. Checker) — это программа, которая на вход получает тест, вывод программы участника и вывод программы жюри и определяет правильность вывода участника. К сожалению, ошибки в чекерах часто приводят к тяжелым последствиям. Далеко не во всех задачах можно просто сравнить ответы на равенство. Например, в задаче 234H - Слияние двух колод в чекере используется декартово дерево. Если по условию задачи требуется сертификат, то чекер лучше всего писать в концепции readAnswer(ans)/readAnswer(ouf). Это концепция и многое другое по теме разработки чекеров описано в древнем посте Чекеры, testlib.h и просто по теме. Чекеры удобно писать с помощью библиотеки testlib.h.

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

В обновленной версии Polygon всё стало значительно лучще! Мы сделали удобные средства для тестирования валидатора и чекера.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +159
  • Проголосовать: не нравится

Codeforces Round #188
Автор yaro, 11 лет назад, По-русски

Добрый вечер, друзья!

За обсуждением животрепещущей темы использования чужого кода в своих решениях можно и не заметить, что приближается зима 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)!

Доступны результаты первого дивизиона, результаты второго дивизиона.

Разбор.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +331
  • Проголосовать: не нравится

ABBYY Cup 3.0 Разборы
Автор ruzana.miniakhmetova, 11 лет назад, По-русски

Друзья, вот и закончился онлайн-тур ABBYY Cup 3.0!

Спасибо большое всем участникам! Мы приносим свои извинения за проблемы с тестированием. MikeMirzayanov всех уже обрадовал планами о закупке тестирующих машин. Надеемся, что в будущем таких ситуаций не повторится.

А вот и разборы задач:

Задача "Спецзадание"

Это была одна из самых простых задач из предложенных. Решение задачи сводится к рассмотрению нескольких случаев. Изначально ответ равен единице. Заметим, что если в строке встречается "?", то он увеличивает число возможных кодов в 10 раз. За исключением случая, когда "?" стоит в начале строки. Тогда он увеличивает число возможных кодов в 9 раз. Далее нужно рассмотреть случаи, когда среди символов строки встречаются буквы. Тут нужно рассмотреть два случая:

  • Первый символ строки не буква. Тогда нужно просто умножить ответ на число размещений десяти цифр по количеству различных букв в строке.
  • Первый символ строки буква. Тогда нужно просто умножить ответ на 9 и на число размещений девяти цифр по N - 1, где N – это количество различных букв в строке.

    Заметим, что в данной задаче необязательно реализовывать длинную арифметику. Так как все операции за исключением умножения на 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
    • Проголосовать: нравится
    • +93
    • Проголосовать: не нравится

    Умный Бобер ждет вас на ABBYY Cup 3.0!
    Автор ruzana.miniakhmetova, 11 лет назад, По-русски

    UPD2: Дорогие участники!

    Как мы и обещали, лучших 25 участников по результатам онлайн-тура ABBYY Cup 3.0 и победителей конкурса задач мы приглашаем на День открытых дверей ABBYY, который состоится 17 июля в московском офисе ABBYY. Всем гражданам РФ мы предоставим полную компенсацию дороги туда-обратно (по предварительному согласованию суммы), с остальными победителями вопрос компенсации будет обсуждаться индивидуально.

    Дорогие победители, напишите, пожалуйста, в течение 5 дней нам на электронный ящик [email protected] о своем желании приехать.

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

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

    UPD1: Разборы!

    UPD: Друзья, уже сегодня состоится онлайн-тур ABBYY Cup 3.0!

    На всякий случай, несколько замечаний:

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

    Приятного всем контеста!

    Всем привет!

    Мы рады анонсировать долгожданный 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 лучших, не являетесь победителем конкурса задач и никогда не были у нас на Дне открытых дверей, но хотите приехать, напишите нам о своем желании на [email protected] в течение 5 дней после контеста. Мы обязательно постараемся вас пригласить. Что такое День открытых дверей ABBYY и как он проходил в 2011 г. и в 2012 г. в блоге Alex_KPR.

    Как всегда, результаты ABBYY Cup могут быть зачтены как первый этап собеседования при трудоустройстве в ABBYY или при поступлении в магистратуру ABBYY в МФТИ.

    • Полный текст и комментарии »

    Анонс ABBYY Cup 3.0
    • Проголосовать: нравится
    • +173
    • Проголосовать: не нравится

    ICPC Challenge 2013
    Автор NALP, 11 лет назад, перевод, По-русски

    Всем привет!

    Я надеюсь, никто не забыл, что каждый год перед 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!

    Вы можете найти больше информации тут и тут.

    Мы будем рады видеть каждого из вас :)

    Удачи!

    Полный текст и комментарии »

    • Проголосовать: нравится
    • +143
    • Проголосовать: не нравится

    Codeforces Round #187
    Автор Sereja, 11 лет назад, По-русски

    Всем привет!

    Совсем скоро, 7 июня в 19:30 MSK состоится Codeforces Round #187, автором которого являюсь я. Это мой седьмой раунд на Codeforces и я надеюсь, что не последний.

    Спасибо Геральду Агапову (Gerald), Роману Фурко(Furko) и Аксенову Виталику(Aksenov239) за помощь в подготовке раунда и Марии Беловой (Delinur) за перевод условий на английский.

    Настоятельно рекомендую прочитать условия ВСЕХ задач.

    Gl & hf ! :)

    Разбор.

    Полный текст и комментарии »

    • Проголосовать: нравится
    • +200
    • Проголосовать: не нравится