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

Недавно я добавил 46-той контест Андрея Станкевича в Тренировки. Теперь все контесты есть в тренировках. Вот полный список и группа со всеми контестами.

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

Всем привет!

В этом году мы в третий раз проводим мероприятие Russian AI Cup, на этот раз 2014. Участникам предстоит программировать искусственный интеллект для команды хоккеистов и соревноваться с программами других участников в матчах, в которых принимают участие от 2 до 6 хоккеистов с каждой стороны.

Сегодня состоялся релиз соревнования. Поучаствовать в мероприятии можно тут: http://russianaicup.ru. Удачи!

436A - Feed with Candy

Автор разбора: Fefer_Ivan

В задача А типы съеденных конфет должны все время менятся. Так что первая съеденная конфета определяет тип всех последующих конфет. Возможных типа всего два, так что переберем тип первой съеденной конфеты. Пусть в какой-то момент времени Ом Ном должен съесть конфету типа t и может прыгать на высоту h. Очевидно, что наиболее выгодным решением будет съесть конфету с наибольшей массой среди всех конфет, которые Ом Ном может съесть на текущем этапе. Для решения задачи необходимо промоделировать процесс поедания конфет для начального h = x и t = [0, 1] и выбрать лучшее значение.

436B - Om Nom and Spiders

Автор разбора: Fefer_Ivan

Пронумеруем столбцы таблицы начиная с 0 слева направа, а строки начиная с 0 сверху вниз. Теперь заметим, что в момент времени t > 0 в клетке (x, y) могут находиться только 4 паука:

• Паук, который движется влево и в начале был в клетке (x, y + t).
• Паук, который движется вправо и в начале был в клетке (x, y - t).
• Паук, который движется вниз и в начале был в клетке (x - t, y).
• Паук, который движется вверх и в начале был в клетке (x + t, y).

Давайте переберем столбец в котором Ом Ном начнет свой путь. Пусть это столбец y. В момент времени 0 все пауки стоят на своих исходных позициях, а Ом Ном стоит в клетке (0, y). Так как на нулевой строке нет пауков, то в момент времени 0 Ом Ном их точно не встречает. Когда Ом Ном находится в клетке (x, y), это значит, что с момента начала движения прошло x единиц времени. Следовательно, для того, чтобы вычислить сколько пауков Ом Ном встретим в этой клетке, необходимо проверить лишь 4 клетки, указанные выше, на наличие паука, движущегося в нужном направлении.

436C - Dungeons and Candies

Автор разбора: Fefer_Ivan

Давайте рассмотрим неориентированный взвешенный граф, в котором k + 1 вершина. Пронумеруем вершины целыми числами от 0 до k. Вершины c 1 по k будут соответствовать уровни. Для каждой пары уровней i и j добавим ребро из i в j стоимость которого равно стоимости передачи одного уровня как разность с другим. Так же для каждого уровня i добавим ребро между вершиной 0 и i стоимости n·m, т.е. стоимости передачи уровня целиком. Каждый способ передать все уровни соответсвует остовному дереву в указанном графе. Таким обзаром необходимо вывести минимальное остовное дерево в этом графе.

436D - Pudding Monsters

Автор разбора: Fefer_Ivan

Задача решается при помощи динамического программирования. Введем обозначения: sum(l, r) — количество особых клеток на отрезке с l по r, z_i — максимальное количество особых клеток, которые можно покрыть, используя только первые i монстров при условии, что i-тый монстр либо остается на месте, либо отправляется влево, d_i--- максимальное количество особых клеток, которые можно покрыть, используя только первые i монстров при условии, что i-тый монстр остается на месте.

Рассмотрим процесс вычисления d_i. Пусть i-тый монстр находится в клетке r. Переберем самую левую особую клетку, которая будет покрыта блоком монстров, в котором будет находиться i-й монстр. Пусть эта особая клетка находится в клетке l. Тогда нам требуется r - l дополнительных монстров отправить вправо для того, чтобы покрыть эту особую клетку. Тогда ответ будет равен z_{i - (r - l)} + sum(l, r). Для вычисления d_i надо взять максимум по всем особым клеткам, левее i-того монстра.

Теперь, после того, как мы вычислили очередное значение d_i, необходимо обновить некоторые значения z_j. Пусть i-тый монстр находится в клетке l. Переберем самую правую особую клетку, которая будет покрыта блоком монстров, в котором будет находиться i-й монстр. Пусть эта особая клетка находится в клетке r. Тогда нам требуется r - l дополнительных монстров отправить влево для того, чтобы покрыть эту особую клетку. Тогда, z_{i + (r - l)} можно обновить следующим значением d_i + sum(l + 1, r). Так же необходимо не забыть обновить значение z_i значением z_i - 1.

Как можно видеть это решение имеет сложность O(n·m), так как для каждого из n монстров мы перебираем все m особых клеток, а все вычисления при фиксированной паре монстр-клетка проходят за O(1).

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

436E - Cardboard Box

Автор разбора: Gerald

В задаче E нужно было написать правильную жадность. Правильных жадностей существует несколько, вот одна из них:

• Посмотрим на некоторый оптимальный ответ (набор как-то пройденных уровней). Отсортируем все уровни по b[i]. Если рассмотреть последний взятый в ответ уровень, пройденный на 2 звезды, то окажется, что все находящиеся до него в таком порядке уровни пройдены хотя бы на одну звезду. Иначе, можно было бы заменить этот уровень на какой-то не пройденный и не увеличить ответ.
• Пользуясь вышесказанным, зафиксируем префикс L уровней в порядке сортировки по b[i]. Все уровни этого префикса мы должны хоть как-то пройти (либо на 1, либо на 2 звезды). Дополнительно, будет считать, что все уровни пройденные на 2 звезды должны содержаться только в этом префиксе (такой префикс должен существовать для некоторого оптимального ответа, как было показано ранее).
• Так как мы зафиксировали префикс длиной L уровней, которые мы точно хоть как-то пройдем, можно сказать, что нам осталось добрать w - L звезд. Как мы можем добирать эти звезды? Либо допроходить какие-то уровни из префикса L на 2 звезды, либо проходить уровни не из префикса L на одну (потому что уровни, которые мы проходим на 2 звезды должны содержаться только на зафиксированном префиксе).
• Понятно, что для того, чтобы получить оптимальный ответ нужно выбрать w - L самых дешевых звезд. Поэтому отсортируем n элементов: L чисел b[i] - a[i] (для всех i ≤ L), n - L чисел a[i] (для всех i > L). Выберем среди этих чисел w - L минимальных.

Описанное нужно было реализовывать быстрее, чем за квадрат. Самая очевидная реализация использует декартово дерево, чуть менее очевидная использует дерево отрезков.

Итоговая сложность решения: O(n log n).

436F - Banners

Автор разбора: Gerald

Задача F была самой сложной задачей контеста. Чтобы лучше представить себе ее решение, можно перейти к геометрическому представлению задачи. Представим, что люди — это точки на плоскости Opc, тогда, то что требуется найти — для каждой прямой c = i, такую прямую p = j, что некоторая функция принимает максимальное значение. Под некоторой функцией понимается следующая: (количество точек не ниже прямой c = i умножить на w·i) плюс (количество точек ниже прямой c = i и не левее прямой p = j умножить на j).

Будем двигать сканирующую прямую снизу вверх. Сначала рассматриваем c = 0, затем c = 1 и так далее. При этом для каждого p будем хранить величину d[p] — чему равен ответ на задачу при текущем c, если второй параметр будет равен p. Если у нас есть корректно посчитанный массив d[] и мы переходим от c к c + 1, как пересчитать этот массив для нового c?

Посмотрим на всех людей, для которых хоть что-то поменяется, очевидно — это люди у которых b[i] = c. При текущем c они еще пользовались бесплатной версией, но после увеличения на 1, они перестанут ей пользоваться. Понятно, что каждый такой человек i модифицирует массив следующим образом: d[1] +  = 1, d[2] +  = 2, ..., d[b[i]] +  = b[i].

Теперь можно переформулировать задачу в терминах структур данных. Есть два вида запросов: прибавить на префиксе возрастающую арифметическую прогрессию, узнать максимум среди всех элементов массива d. Один из способов решить такую задачу — корневая декомпозиция.

Разобьем все запросы на группы по sqrt(q) штук, в каждой группе выделим отрезки, на которых к ячейке d[i] значение i прибавляется с одним и тем же коэффициентом. Для каждого такого отрезка построим нижнее огибающее множество прямых y = d[i] + i·x. Так как запросов в группе sqrt(q), то и отрезков будет O(sqrt(q)). Значит прибавление на префиксе и взятие максимума можно будет делать за O(sqrt(q)).

Итоговая сложность решения: O(MAXX·sqrt(MAXX)), где MAXX — максимальное значение среди a[i] и b[i].

Добрый день.

Сегодня я разбирался с NullPointerException, возникающим в API в крайне непонятном месте, и обнаружил, что следующий код ведет себя странно.

long a = 0; // primitive long
Long b = null; // Long object
boolean s = ???;

Long c = s ? a : b;

Выяснилось, что s ? a : b эквивалентно s ? a : (throw new NullPointerException). И связано это с тем, что выражение s ? a : b имело тип long, а не Long и так как переменная b имела значение null, то при попытке привести её к типу long возникал NPE. Такие дела. Баг я поправил так

Long c = s ? Long.valueOf(a) : b;

С уважением, Иван.

P.S.
Все как и написано в спецификации:

• If one of the second and third operands is of primitive type T, and the type of the other is the result of applying boxing conversion (§5.1.7) to T, then the type of the conditional expression is T.

http://docs.oracle.com/javase/specs/jls/se7/html/jls-15.html#jls-15.25

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

Сегодня мы представляем вам Codeforces API. Благодаря этому разделу, вы сможете получать часть данных Codeforces в машинно-читаемом JSON-формате.

У API есть подробная инструкция по адресу /apiHelp, которая поддерживается актуальной. У каждого метода есть пример URL, которым можно воспользоваться для просмотра примера результата метода и экспериментов с параметрами.

По умолчанию, любой запрос к API будет анонимным, и ему будут доступны только публичные данные. Чтобы сделать запрос не анонимным, надо создать API-ключ на странице /settings/api и воспользоваться нижней частью инструкции по адресу /apiHelp.

На данный момент все методы API лишь читают данные. Добавление write-методов вида "послать решение" планируется.

Мы открыты для предложений и запросов о новых API-методах. Особенно, от авторитетных членов олимпиадного сообщества.

С уважением, Иван.

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

UPD: Раунд завершен. Всем большое спасибо за участие. Финальные результаты.

Сегодня мы хотим провести тестовый и нерейтинговый раунд по необычным правилам. С вашей помощью мы хотели бы проверить новые правила, новый вид задач и работу Codeforces внутри тега <iframe>.

Старт запланирован на 20:00, появится специальная ссылка, чтобы войти в контест.

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

Перейти к контесту!

В соревновании будет два вида задач: логические задачи и программистские задачи.

Логические задачи сделаны для того, чтобы их можно было решить без написания кода (но никто не запрещает его написать). Логическая задача состоит из нескольких тестов, каждый из которых стоит определенное количество баллов.
Ответ на каждый тест может посылаться отдельно. Для ответа на тест логической задачи необходимо ввести ответ в соответствующее поле или выбрать один или несколько предложенных вариантов. Ответ можно изменять и посылать любое количество раз. По каждому тесту проверяется только последний ответ. Такие задачи проверяются после окончания соревнования.

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

Соревнование будет длиться 1.5 часа. Для каждого участника соревнование разделено на два этапа: Normal Time (NT) и Extra Time (ET).

Этап Normal Time длится не более 30 минут с того момента, как участник нажимает на кнопку "Start Contest". Если участник начнет соревнование менее чем за 30 минут до конца, то его время сократится соответствующим образом. Баллы, набранные участником на этом этапе являются главным критерием оценки. Участник, набравший в этап Normal Time большее количество баллов будет выше, чем участник, набравший меньшее количество.

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

Два участника в первую очередь сравниваются по количеству баллов, набранных на этапе Normal Time. При равенстве сравниваются баллы, набранные в Extra Time. При равенстве и этих баллов сравнивается время последней попытки, которая увеличила количество баллов у участника. Для программистских задач будет использована посылка, набравшая наибольшее количество баллов. Если таких посылок несколько, будет использована самая ранняя. Для логических задач будет использовано время ответа на каждый из тестов. Внимание: если вы ответили на один из тестов в Normal Time, а на этапе Extra Time решили изменить ответ, то после повторной посылки баллы за этот тест будут считаться, как набранные в Extra Time.

Задачи будут относительно простые, но, я надеюсь, интересные, как и формат соревнования.

Мы будем очень благодарны членам сообщества, которые помогут нам в тестировании.

С уважением, Иван.

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

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

Ключевой возможностью является Codeforces Premium.

• Вам не хватает рейтинга для создания тренировок?

• Вы хотите создать открытую группу из Div.2?

• Решения за O(n²) никак не проходят в Time Limit?

• Раунды полны безысходности?

Добрый вечер, Codeforces.

UPD: Новая функциональность недоступна до окончания раунда. В будущем она не будет отключаться на время раундов

Сегодня мы представляем вам предновогоднее обновление, главной новой функцией которого являются мэшапы.

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

Сегодня функциональность групп была обновлена и расширена.

Вот краткий список изменений:

• Появилась возможность прикреплять к группе записи из личного блога.

• Появилась возможность создавать записи прямо в блоге группы. Эта запись не будет видна в прямом эфире и голоса за неё или за комментарии к ней не будут влиять на вклад.

• Создавать или прикреплять к группе записи могут только менеджеры. Комментировать эти записи могут любые члены группы.

• Появился новый вид участника группы: зритель. Зритель – это член группы, который не может зарегистрироваться на соревнование группы и не отображается в таблице результатов группы. Зритель может смотреть результаты и задачи, а так же читать и комментировать блог группы. Например, если вы хотите, чтобы кто-либо мог наблюдать за тренировками вашей группы, но не смог писать их, можно его пригласить как зрителя.

• Политика регистрации зрителей может принимать те же значения, что и политика регистрации участников. Политика регистрации зрителей не может быть более строгой, чем политика регистрации участников. По умолчанию она установлена в то же значение, что и политика регистрации участников.

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

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

С уважением, Иван.

Привет, Codeforces!

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

Как создать группу

Чтобы создать группу необходимо иметь рейтинг участника Div. 1. Если у вас есть возможность создать группу, то на странице Группы у вас будет соответствующая ссылка.

При создании группы кроме названия можно указать:

• описание — может содержать простой HTML,
• логотип — будет сиять на каждый странице вашей группы,
• ссылку на внешний веб-сайт группы.

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

Open Cup — это очень крупное и престижное соревнование по программированию, в котором я участвую не первый год. Вклад создателей и авторов Open Cup в развитие спортивного программирования переоценить сложно.

И единственным недостатком этого соревнования является время проведения — воскресенье. Я понимаю, что так как многие из участников уже ветераны, работают и единственный день в который они могут найти 5 часов — это воскресенье.

Но почему бы тогда не начинать раньше утром? Например, в 10 00. Тогда в 3 часа все были бы уже свободны и с чистой совестью могли отдыхать от рабочей недели. Но завтра Open Cup начнется в 12 00, что означает лишь одно — и с утра ничего толкового не сделать, и после уже будет относительно поздно.

Я хотел бы спросить у сообщества, мне одному кажется такое время неудобным? И если я не один, тогда вопрос организаторам, чем именно обосновано время начала и, если конечно есть такая возможность, его можно перенести?

С уважением, Иван.

UPD: Вот она ирония, организаторы будто меня услышали и перенесли контест на час позже. :)

Доброй ночи/рассвета/утра/дня/заката/вечера/ночи, Codeforces!

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

Это обновление сосредоточено вокруг скриптов для генерации тестов.

339A - Математика спешит на помощь

Разбор написан Fefer_Ivan

Для решения этой задачи можно посчитать количество цифр 1, 2 и 3 во входных данных. Пусть в данных c₁ цифр 1, c₂ цифр 2 и c₃ цифр 3. Тогда необходимо вывести последовательность из c₁ цифр 1, c₂ цифр 2 и c₃ цифр 3, разделяя соседние цифры знаком +.

339B - Ксюша и кольцевая дорога

Разбор написан Fefer_Ivan

Для решения этой задачи необходимо быстро вычислять время на перемещение между зданиями a и b. Пусть a ≤ b, тогда Ксения попадет из a в b за b - a шагов. Иначе, т.е. если a > b, Ксении придется ехать через здание с номером 1. Таким образом ей потребуется совершить n - a + b шагов.

339C - Ксюша и гири

Разбор написан Fefer_Ivan

Для решения этой задачи введем понятия баланса. Баланс — это разность суммы весов гирь на левой чаше весов и суммы весов гирь на правой чаше. В самом начале, баланс равен нулю. На каждом шаге Ксения кладет одну гирю на одну из чаш весов, следовательно добавляет или вычитает из баланса число от 1 до 10. Причем на каждом нечетном шаге число добавляется, а на каждом четном — вычитается. При этом по условию после каждого шага баланс не должен быть равен нулю и знак баланса должен изменятся. Из этого следует, что если на каком-то этапе баланс стал больше 10, то продолжить последовательность будет невозможно. Так же по условию нельза использовать одно число два раза подряд. Для решения рассмотрим граф, в котором вершины — это тройки чисел (i, j, k), где i — это текущий баланс, j — это вес, использованный на предыдущем шаге, а k — это номер текущего шага. Дуги этого графа должны соответствовать тому, что Ксения на очередном шаге кладет очередную гирю по условию задачи. Тогда для решения задачи необходимо найти в этом графе путь из вершины (0, 0, 1) до любой вершины вида (x, y, m), где x, y — произвольные числа, а m — это необходимое количество шагов.

339D - Ксюша и битовые операции

Разбор написан Gerald

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

В листьях дерева отрезков будем хранить сами значения a_i. В вершинах, расстояние от которой до листьев равно 1, будем хранить OR чисел в листьях, которые являются сыновьями этой вершины в дереве отрезков. Аналогично, в вершинах, расстояние от которых до листьев равно 2, будет хранить xor чисел, хранящихся в их непосредственных сыновьях. И так далее. Тогда в корне дерева и будет содержаться требуемое значение v.

Для выполнения операции обновления элемента не нужно перестраивать все дерево. Нужно найти путь от корня до листа, который соотвествует позиции обновления, и пересчитать значения только в вершинах дерева отрезков, которые лежат на этом пути. Если все делать правильно, то каждый запрос обновления будет выполняться за O(n). Памяти при этом требуется O(2ⁿ).

339E - Три переворота

Разбор написан Gerald

Будем называть команды из условия операциями реверса, а ряд коней будем называть массив. Неожиданно, да?

Задача решается перебором все возможных вариантов. Для начала предположим, что реверс l = r допустим. Найденное нами решение может содержать такие реверсы. Понятно, что решению задачи это никак не помешает. Посколько такие реверсы можно просто не выводить. Это ничего не ухудшит.

Следующее ключевое утверждение: операции реверса разбивают массив на не более чем 7 отрезков первоначального массива. Другими словами, представим, что массив изначально склеен, а каждая операция реверса вырезает из массива отрезок и переворачивает его. Тогда массив в конце окажется разрезан не более чем на 7 кусочков.

Теперь можно придумать неправильное решение задачи, а потом придумать оптимизацию, которая превращает его в правильное. Переберем как мы разобьем массив и на сколько кусочков. А теперь будет перебирать операции реверса, но при этом операции реверса должны захватывать кусочки только целиком. Понятно, что такое решение правильное, только оно не укладывается в TL.

Как его улучшить? Заметим, что в предыдущем решении конкретное разбиение массива требуется нам только в самом конце перебора для проверки, можно ли с таким разбиением так пореверсить массив, чтобы получить то, что задано в input. Поэтому, давайте считать, что массив изначально как-то разделен на 7 частей, причем некоторые части будут, возможно, пустые. Теперь будет перебирать реверсы как и в наивном решении. Только теперь в том месте, где нужна проверка, мы не будем пользоваться конкретным разбиением, а будем искать такое разбиение на части, что зафиксированные перевороты на таком разбиении дадут наш массив.

Поиск такого разбиения можно выполнить жадно (читателю предоставляется возможность самому подумать как). Авторское решение делает это за количество блоков в разбиении, то есть за 7 операций. Но, можно сделать это и за O(n) — это должно проходить в TL, если написать отсечения в переборе.

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

Сегодня в 19:30 по московскому времени состоится Codeforces Round #197.

Авторами этого раунда являются я и Gerald. Условия переводила Delinur, за что ей моя искренная благодарность. Так же спасибо MikeMirzayanov за созданиe и поддержку Codeforces.

Стоимости задач: 500 — 1000 — 1500 — 2000 — 3000.

Удачи!

UPD: Чтобы сделать анонс более интересным и увлекательным мы считаем необходимым вставить в анонс шутку про коней и фотографию, на которой изображен процесс подготовки раунда.

Воспитательница в детсаду:
- Коновалов, ты зачем сломал Конюхову его игрушечного коня?!

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

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

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

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

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

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

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

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

Сегодня я хотел бы рассказать вам об последних обновлениях на Codeforces.

• Очень часто мы видим комментарии от людей, которые забывают о том, что в некоторых задачах используется файловый ввод/вывод и получают неправильный ответ на первом тесте. Теперь на Codeforces при наличии нестандартного ввода или вывода, нужные имена файлов будут подсвечиваться в условии (например: 254A - Карточки с числами), на основной странице контеста (например: Codeforces Round 155 (Div. 2)) и при посылке решения (например: screenshot).
• Теперь есть возможность просмотра теста, на котором был сделан взлом (например: http://mirror.codeforces.com/contest/292/hacks). Естественно, до окончания контеста она доступна только участнику, который совершил взлом. Обычно, если при взломе был получен вердикт некорректный тест, из короткого сообщения валидатора вида [FAIL Integer parameter equals to 500, violates the range [1, 400) ... довольно сложно понять что именно пошло не так. А проверить, была ли во введенном тесте опечатка было вообще не возможно. Именно для удобства в таких случаях и была создана эта возможность. По ссылке "Показать тест" вы получаете текст теста в чистом виде, если тест был введен вручную, или отчет о генерации теста, если тест использовал генератор. Чистый текстовый формат используется для того, чтобы можно было просто выделить весь тест или отчет при помощи Ctrl + A.
• Были исправлены баги, из-за которых решения на C# не могли работать с файловым вводом/выводом. Кроме этого, был исправлен ряд других, менее критичных багов.
• Попытка с вердиктом "неправильный ответ на взломе 1" раньше не считалась за штрафную. Это тоже был баг. Теперь считается.

На этом пока все, но работа над Codeforces продолжается, и через некоторое время можно будет написать про новую серию улучшений.

С уважением, Иван.

Добрый вечер, Codeforces.

Сегодня в тренировки добавлены первые пять контестов из известной серии Andrew Stankevich Contest. Они полностью доступны для прорешивания и вирутального участия.

По моему опыту участия в Andrew Stankevich Contest'ах я могу сказать, что эти контесты всегда подготовлены качественно, состоят из интересных задач и в них всегда весело и интересно участвовать.

Как говорится, good luck and have fun.

P.S. Все контесты доступны в группе Контесты Андрея Станкевича

Прямые ссылки

Обратите внимание, что все задачи используют различные входные и выходные файлы. Их названия написаны в условиях и на вкладке задачи.

• 2002-2003 Зимние Петрозаводские сборы, Andrew Stankevich Contest 1 (ASC 1)
• 2003-2004 Летние Петрозаводские сборы, Andrew Stankevich Contest 2 (ASC 2)
• 2003-2004 Летние Петрозаводские сборы, Andrew Stankevich Contest 3 (ASC 3)
• 2003-2004 Зимние Петрозаводские сборы, Andrew Stankevich Contest 4 (ASC 4)
• 2003-2004 Зимние Петрозаводские сборы, Andrew Stankevich Contest 5 (ASC 5)
• 2003-2004 Зимние Петрозаводские сборы, Andrew Stankevich Contest 6 (ASC 6)
• 2004-2005 Летние Петрозаводские сборы, Andrew Stankevich Contest 7 (ASC 7)
• 2004-2005 Летние Петрозаводские сборы, Andrew Stankevich Contest 8 (ASC 8)
• 2004-2005 Летние Петрозаводские сборы, Andrew Stankevich Contest 9 (ASC 9)
• 2004-2005 Зимние Петрозаводские сборы, Andrew Stankevich Contest 10 (ASC 10)
• 2004-2005 Зимние Петрозаводские сборы, Andrew Stankevich Contest 11 (ASC 11)
• 2004-2005 Зимние Петрозаводские сборы, Andrew Stankevich Contest 12 (ASC 12)
• 2005-2006 Летние Петрозаводские сборы, Andrew Stankevich Contest 13 (ASC 13)
• 2005-2006 Летние Петрозаводские сборы, Andrew Stankevich Contest 14 (ASC 14)
• 2005-2006 Летние Петрозаводские сборы, Andrew Stankevich Contest 15 (ASC 15)
• 2005-2006 Зимние Петрозаводские сборы, Andrew Stankevich Contest 16 (ASC 16)
• 2005-2006 Зимние Петрозаводские сборы, Andrew Stankevich Contest 17 (ASC 17)
• 2005-2006 Зимние Петрозаводские сборы, Andrew Stankevich Contest 18 (ASC 18)
• 2006-2007 Летние Петрозаводские сборы, Andrew Stankevich Contest 19 (ASC 19)
• 2006-2007 Летние Петрозаводские сборы, Andrew Stankevich Contest 20 (ASC 20)
• 2006-2007 Летние Петрозаводские сборы, Andrew Stankevich Contest 21 (ASC 21)
• 2006-2007 Зимние Петрозаводские сборы, Andrew Stankevich Contest 22 (ASC 22)
• 2006-2007 Зимние Петрозаводские сборы, Andrew Stankevich Contest 23 (ASC 23)
• 2006-2007 Зимние Петрозаводские сборы, Andrew Stankevich Contest 24 (ASC 24)
• 2007-2008 Летние Петрозаводские сборы, Andrew Stankevich Contest 25 (ASC 25)
• 2007-2008 Летние Петрозаводские сборы, Andrew Stankevich Contest 26 (ASC 26)
• 2007-2008 Летние Петрозаводские сборы, Andrew Stankevich Contest 27 (ASC 27)
• 2007-2008 Зимние Петрозаводские сборы, Andrew Stankevich Contest 28 (ASC 28)
• 2007-2008 Зимние Петрозаводские сборы, Andrew Stankevich Contest 29 (ASC 29)
• 2007-2008 Зимние Петрозаводские сборы, Andrew Stankevich Contest 30 (ASC 30)
• 2008-2009 Летние Петрозаводские сборы, Andrew Stankevich Contest 31 (ASC 31)
• 2008-2009 Летние Петрозаводские сборы, Andrew Stankevich Contest 32 (ASC 32)
• 2008-2009 Зимние Петрозаводские сборы, Andrew Stankevich Contest 33 (ASC 33)
• 2008-2009 Зимние Петрозаводские сборы, Andrew Stankevich Contest 34 (ASC 34)
• 2009-2010 Летние Петрозаводские сборы, Andrew Stankevich Contest 35 (ASC 35)
• 2009-2010 Летние Петрозаводские сборы, Andrew Stankevich Contest 36 (ASC 36)
• 2009-2010 Зимние Петрозаводские сборы, Andrew Stankevich Contest 37 (ASC 37)
• 2010-2011 Летние Петрозаводские сборы, Andrew Stankevich Contest 38 (ASC 38)
• 2010-2011 Зимние Петрозаводские сборы, Andrew Stankevich Contest 39 (ASC 39)
• 2011-2012 Летние Петрозаводские сборы, Andrew Stankevich Contest 40 (ASC 40)
• 2011-2012 Зимние Петрозаводские сборы, Andrew Stankevich Contest 41 (ASC 41)
• 2012-2013 Летние Петрозаводские сборы, Andrew Stankevich Contest 42 (ASC 42)
• 2012-2013 Зимние Петрозаводские сборы, Andrew Stankevich Contest 43 (ASC 43)
• 2013-2014 Летние Петрозаводские сборы, Andrew Stankevich Contest 44 (ASC 44)
• 2013-2014 Зимние Петрозаводские сборы, Andrew Stankevich Contest 45 (ASC 45)
• 2014-2015 Летние Петрозаводские сборы, Andrew Stankevich Contest 46 (ASC 46)
• UPD 2014-2015 Зимние Петрозаводские сборы, Andrew Stankevich Contest 47 (ASC 47)

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

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

Теперь вы можете указать в своем социальном профиле (http://mirror.codeforces.com/settings/social) название организации, которую вы представляете.

Это может быть как ВУЗ, так и школа или любая другая коммерческая или не очень организация. Если вы хотите указать школу, лицей или гимназию, так же укажите город, чтобы избежать неоднозначности. Например, вместо ФТЛ №1, укажите Саратов, ФТЛ №1.

Пожалуйста, при заполнении поля Организация используйте автодополнение и следуйте подсказкам. Иначе возникнет путаница. А распутывать придется при помощи TRUNCATE TABLE.

Наверняка, одну и ту же организацию можно назвать разными способами. Особенно это верно для ВУЗов. Старайтесь использовать не очень короткие имена, так как они могут привести к неоднозначности. Например: СГУ — это Саратовский, Самарский или Сыктывкарский университет?

Правда, слишком длинные название тоже лучше не использовать. Вы представляете что будет, если tourist решит написать полное название Saint Petersburg State University of Information Technologies, Mechanics and Optics? : )

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

Поздравляем представителей Самарского ГАУ, которые на момент написания поста занимали первое и единственное место в рейтинге организаций.

С уважением, Иван.

Привет всем болельщикам.

Говорят, что можно посмотреть на камеру отдельной команды. Как это точно сделать?
Спасибо.

Забавный баг. А вы пишете контест 32 марта?

Доброе время суток, Codeforces.
Это выдержки из того, о чем мы обычно болтаем после контеста.
Все случаи реальные. Имена, контесты и задачи в явном виде не упоминаются.

Поехали.

Петя:"5 минут до конца. -8 по задаче. Весь код перечитал, весь алгоритм перепроверил. Думаю, а может не надо в конце строки пробел выводить. Убрал — прошло. Встал и закричал со злости, что авторы редиски и что хвостовой пробел убрал и accepted".

Вася:"5 минут до конца. -6 по задаче. Весь код перечитал, весь алгоритм перепроверил. Тут слышу крик Пети. Тоже убрал — тоже прошло".

Имеется в виду пробел, возникающий при выводе массива чисел следующим образом:forn(i, n) printf("%d ", a[i])

--- А как решать задачу А?
--- Ты же её сдал на контесте.
--- Ну я какую-то фигню сдал, как её нормально решать?

Автор контеста: "Блин, все решения: разбить отрезок [0, 2*PI] на MAGIC кусков и в каждом тернарный поиск. А я в авторском зачем-то все по-честному упирал в крайние точки, вращал, сортировал события..."

--- А вы тоже получали минуса по задаче, где в input'е n и m перепутаны?
--- А что это за задача была?
--- Ну где n и m перепутаны.

--- Для решения этой задачи необходимо триангулировать многоугольник. Это можно сделать методом отрезания ушей.
--- Подожди, там же многоугольник выпуклый?
--- Нет, там даже 3-й сэмпл не выпуклый.
--- А как у нас тогда прошло?

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

UPD. Спросил у Edvard. Он ответил, что такой функциональности нет.

Хотел бы узнать есть ли у кого запись, которую проводила mail.ru на NEERC в этом сезоне? Можно ли где-нибудь её скачать? Заранее благодарен.

Доброе утро/день/вечер, Codeforces.

*Предыдущий пост: http://mirror.codeforces.com/blog/entry/3853 *

Следуя совету al13n (http://mirror.codeforces.com/blog/entry/3853#comment-79329 ), для новой тонкости я создал новый пост, чтобы не возникало путаницы с комментариями.

20.02.12 Источник: от кого-то когда-то слышал, сейчас проверил, оказалось интересно
Оператор >> для знаковых типов сохраняет знак. То есть если вы сдвинете вправо отрицательное число, то слева будут дописаны 1, а если положительное — то 0. При сдвиге влево всегда дописывается 0. Меня это как-то не коснулось, потому что в задачах с битовыми масками размера больше 30 я всегда использовал unsigned long long.
Вот код, которым я это проверял:

#include <cstdio>

using namespace std;

inline void printBits(unsigned a){
    for(int i = 31; i >= 0; --i)
        printf(((a >> i) & 1) ? "1" : "0");
    puts("");
}

template<class X> void testShift(X a){
    printf("Before:\n");
    printBits(a);
    a = (a << 1);
    printf("After:\n");
    printBits(a);
    puts("");
}

int main(){

    printf("Signed 15\n");
    testShift(15);
    printf("Signed -15\n");
    testShift(-15);

    printf("Unsigned 15\n");
    testShift(unsigned(15));  
    printf("Unsigned -15\n");
    testShift(unsigned(-15));

    return 0;
}

http://ideone.com/Kc8fI

Продолжение следует...

Доброе утро/день/вечер, Codeforces.

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