Всем привет!

Надеюсь все уже успели оправиться от революции цветов и званий и даже, может быть, попробовать написать раунд в новом для себя положении. Последний раунд собрал космическое количество народу: 8000 человек! И, не побоюсь это сказать, с технической точки зрения раунд прошёл без малейших нареканий! Будем считать, что 15-минутный перенос контеста был частью нашего хитрого плана по достижению рекорда :)

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

Зайдя на страницу с соревнованиями, вы можете теперь видеть список авторов каждого из раундов! Более того, в профиле у человека теперь есть пункт "проблемсеттинг", по которому можно посмотреть на список всех контестов, к подготовке которых человек имел отношение.

Endagorion, например, выглядит так.

Прошедшая сегодня революция цветов и званий представила новый цвет для легендарных гроссмейстеров (в чём-то схожий по смыслу с таргетами на TopCoder), сейчас он из себя представляет первую чёрную букву.

В моём браузере под моей операционной системой (Chrome и Linux Mint) это выглядит, IMHO, скорее как дефект вёрстки, чем как клёвый эффект:

Мне больше хотелось бы видеть что-то наподобие следующего:

Что вы думаете по этому поводу? Пишите в комментариях свои мысли и делитесь своим видением, как должны выглядеть крутейшие-программисты-всех-времён :) Главное требование — вариант не должен выбиваться из стиля CodeForces.

Прошедший VK Cup дал всем нам повод попробовать необычный формат соревнования, когда участники пишут тур командами по два человека. Занимаясь подготвкой онлайн-раундов, финала и трансляции финала соревнования, мы обнаружили множество нюансов и тонких мест, которые стоит учитывать при проведении подобных соревнований, однако для полноты картины нам не хватает фидбека со стороны участников.

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

Нас интересуют любой фидбек об отборочных турах к VK Cup, о финале соревнования от финалистов и о траснляции финала, которая состоялась вчера.

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

562A - Логистические вопросы

(в трансляции: 566C - Логистические вопросы)

Формализуем задачу. Нам дано необычное определение расстояния по дереву: ρ(a, b) = dist(a, b)^1.5. У каждой вершины есть её вес w_i. Нужно как-то так выбрать место x для проведения соревнования, чтобы минимизировать сумму взвешенных расстояний от всех вершин до неё: f(x) = w₁ρ(1, x) + w₂ρ(x, 2) + ... + w_nρ(x, n).

Давайте изучим свойства функции f(x). Мысленно разрешим себе ставить точку x не только в вершины дерева, но и в любую точку на ребре, доопределив естественным образом расстояние от точки внутри ребра до всех остальных вершин (например, середина ребра длины 4 находится на обычном расстоянии 2 от концов ребра).

Утверждение 1. На любом пути в дереве функция ρ(i, x) является выпуклой вниз. Действительно, функция dist(i, x) на любом пути выглядит как график функции abs(x), то есть сначала линейно убывает до ближайшей к i точки на пути [a, b], а потом линейно возрастает. Взяв композицию с выпуклой возрастающей функциея t^1.5, как нетрудно видеть, мы снова получим выпуклую вниз на пути функцию. Здесь под функцией на пути мы подразумеваем обычную функцию действительной переменной x, где под x мы подразумеваем координату точки x на пути [a, b], или, что то же самое, dist(a, x). Таким образом, каждое из слагаемых в определении функции f(x) выпукло вниз на любом пути в дереве, а значит и функция f(x) выпукла на любом пути в дереве.

Будем называть функции, выпуклые вниз на любом пути в дереве выпуклыми на дереве. Сформулируем пару утверждений про выпуклые функции на дереве.

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

Таким образом, у выпуклой вниз функции f(x) есть единственный локальный минимум на дереве, совпадающий с глобальным.

Утверждение 3. Из каждой вершины v дерева существует не более одного ребра, при движении по которому функция убывает. Действительно, в противном случае, если рассмотреть путь, образованный двумя такими рёбрами, то в точке, соответствующей вершине v, функция не будет выпукла вниз.

Назовём направление ребра из вершины v, при движении по которому убывает функция, градиентом функции f в точке x. Согласно утверждению 3, у выпуклой вниз функции f в любой вершине либо однозначно определён градиент, либо вершина является минимумом (глобальным).

Предположим, мы умеем некоторым образом эффективно искать направление градиента из вершины v. Научимся, пользуясь этим знанием и утверждениями 2 и 3 находить глобальный минимум. Если бы наше дерево представляло собой бамбук, то задача бы стала обычной одномерной задачей минимизации выпуклой функции, которая эффективно решается бинарным поиском, т. е. дихотомией. Нам же нужен некоторый эквивалент дихотомии на дереве. Что же это за эквивалент?

Воспользуемся centroid decmoposition! Действительно, возьмём центр дерева (т. е. такую вершину, что размеры всех её поддеревьев не превосходят n / 2). По утверждению 3 можно рассмотреть градиент функции в центре дерева. Во-первых, у функции может не оказаться градиента в центре дерева, что значит, что мы уже нашли оптимум. Иначе, мы знаем, что глобальный минимум расположен именно в поддереве в направлении градиента, значит все остальные поддеревья и сам центр можно выбросить из рассмотрения и оставить только выбранное поддерево. Таким образом, за один подсчёт градиента мы сократили в два раза количество вершин в рассматриваемой части дерева.

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

Теперь научимся считать направление градиента в вершине v. Зафиксируем одно поддерево u_i вершины v. Рассмотрим производную всех слагаемых, соответствующих поддереву u_i при движении в поддерево u_i, и обозначим её за der_i. Тогда, как нетрудно видеть, производная f(x) при движении от x = v в сторону поддерева u_i есть  - der₁ - der₂ - ... - der_i - 1 + der_i - der_i + 1 - ... - der_k, где k — степень вершины v. Таким образом, мы можем за один запуск обхода из вершины v определить все вершины der_i, а значит, и направление градиента, найдя с помощью формулы выше направление, в котором производная функции отрицательна.

Таким образом, получилось решение за .

562B - Клика в графе делителей

(в трансляции: 566F - Клика в графе делителей)

Упорядочим числа в искомой клике по возрастанию. Заметим, что чтобы множество X = {x₁, ..., x_k} образовывало клику, необходимо и достаточно, чтобы для (1 ≤ i ≤ k - 1). Таким образом, нетрудно сформулировать задачу динамического программирования: D[x] есть длина наибольшей подходящей возрастающей подпоследовательности, заканчивающейся в числе x. Формула пересчёта: по всем x, лежащим в A.

Если оформлять задачу динамического программирования в виде динамики "вперёд", то легко оценить сложность получившегося решения: в худшем случае количество переходов есть .

562C - Восстановление карты

(в трансляции: 566E - Восстановление карты)

Назовём окрестностью вершины — множество, состоящее из вершины и всех близких к ней вершин. Таким образом, нам известен набор окрестностей всех вершин в некотором произвольном порядке, причём каждая окрестность также перечислена в произвольном порядке.

Назовём вершину дерева внутренней, если она не является листом дерева. Аналогично, назовём ребро дерева внутренним, если оно соединяет две внутренних вершины. Заметим, что если две окрестности пересекаются ровно по двум элементам a и b, то a и b обязаны быть соединены ребром, причём ребро (a, b) является внутренним. Наоборот, любое внутреннее ребро (a, b) может быть найдено как пересечение каких-то двух окрестностей С и D двух вершин c и d, таких что в дереве есть путь c – a – b – d. Таким образом, мы можем найти все внутренние рёбра, рассмотрев попарные пересечения всех окрестностей. Это можно сделать за время порядка n³ / 2 наивно, либо в 32 раза быстрее, воспользовавшись битовым сжатием.

Заметим, что зная все внутренние рёбра, мы можем узнать все внутренние вершины, за исключением случая, когда граф представляет из себя звезду (т. е. вершину, к которой подцеплены все остальные). Случай звезды нужно разобрать отдельно.

Теперь мы знаем все листы, все внутренние вершины и структуру дерева на внутренних вершинах. Осталось только определить для каджого листа, к какой внутренней вершине он подцеплен. Это можно сделать следующим образом. Рассмотрим лист l. Рассмотрим все окрестности, его содержащие. Рассмотрим минимальную по включению окрестность — утверждается, что это есть окрестность L, соответствующая самому листу l. Рассмотрим все внутренние вершины в L. Их не может быть меньше двух. Если их три или более, то мы можем однозначно определить, к какой из них надо подцепить l — это должна быть та вершина из них, которая имеет степень внутри L больше единицы. Если же их ровно две (скажем, a и b), то определить, к кому из них надо подцепить l, несколько сложнее.

Утверждение: l должна быть подсоединена к той из двух вершин a и b, у которой степень по всем внутренним рёбрам — ровно один. Действительно, если бы l была подсоединена к вершине со внутренней степнью два или более, мы бы рассмотрели этот случай ранее.

Если же у обоих вершин a и b внутренняя степень — 1, то наш граф имеет вид гантели (ребро (a, b), и все остальные вершины, подцепленные либо за a, либо за b). Такой случай также придётся разобрать отдельно.

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

562D - Реструктуризация компании

(в трансляции: 566D - Реструктуризация компании)

Эта задача допускает множество решений с разными асимптотиками. Опишем решение за .

Рассмотрим сначала задачу, в которой присутствуют только запросы второго и третьего типа. Её можно решить следующим образом. Отметим всех работников в ряд на прямой от 1 до n. Заметим, что отделы представляют собой отрезки из подряд идущих работников. Будем поддерживать эти отрезки в любой логарифмической структуре данных, например в сбалансированном дереве поиска (std::set или TreeSet). Объединяя все отделы с позиции x по позицию y, вытаскиваем все отрезки, попавшие в диапазон [x, y] и сливаем их. Для ответа на запрос третьего типа проверяем, лежат ли работники x и y в одном отрезке. Таким образом, мы получаем решение более простой задачи за на запрос.

Добавляя запросы первого типа мы на самом деле разрешаем некоторым отрезкам на прямой относиться к одному и тому же отделу. Добавим в решение систему непересекающихся множеств, которая будет поддерживать классы эквивалентности на отрезках. Теперь запросы первого типа можно реализовать как вызов merge в системе непересекающихся множеств от номеров отделов, к которым принадлежат сотрудники x и y. Также в запросах второго типа надо не забывать вызывать merge от всех удаляемых отрезков.

Получилось решение за время .

562E - Макс и Мин

(в трансляции: 566G - Макс и Мин)

Сформулируем задачу в геометрической интерпретации. У Макса и у Мина есть набор векторов из первой координатной четверти на плоскости и точка (x, y). За свой ход Макс может прибавить любой из имеющихся у него векторов к (x, y), а Мин — вычесть. Мин хочет добиться, чтобы точка (x, y) оказалась строго в третьей координатной четверти, Макс пытается ему помешать. Обозначим вектора Макса за Mx_i, вектора Мина за Mn_j.

Сформулируем очевидное достаточное условие для Макса, чтобы тот мог выиграть. Рассмотрим некоторое неотрицательное направление на плоскости, т. е. вектор (a, b), такой что a, b ≥ 0, при этом хотя бы одно из чисел a, b — не ноль. Тогда если среди ходов Макса есть такой вектор Mx_i, что он не короче всех векторов Мина Mn_j вдоль направления (a, b), то Макс может гарантировать себе победу. Здесь под длиной вектора v вдоль направления (a, b) подразумевается скалярное произведение вектора v на вектор (a, b).

Действительно, пусть Макс постоянно ходит в этот вектор Mx_i. Тогда за пару ходов Макса и Мина точка (x, y) сдвинется на вектор Mx_i - Mn_j для некоторого j, а значит её сдвиг вдоль вектора (a, b) составит ((Mx_i - Mn_j), (a, b)) = (Mx_i, (a, b)) - (Mn_j, (a, b)) ≥ 0. Значит, так как исходно скалярное произведение ((x, y), (a, b)) = ax + by > 0, то и в любой момент времени ax + by будет строго положительно. А значит, Мин ни в какой момент времени не сможет добиться чтобы x и y стали оба отрицательными (так как это значило бы, что ax + by < 0).

Теперь сформулируем некоторый вариант обратного утверждения. Пусть вектор Макса Mx_i лежит строго внутри треугольника, образованного векторами Мина Mn_j и Mn_k. При этом, вектор Mx_i не может лежать на отрезке [Mn_j, Mn_k], но может быть коллинеарен одному из векторов Mn_j и Mn_k.

Заметим, что раз Mx_i лежит строго внутри треугольника, натянутого на Mn_j и Mn_k, то его можно продлить до вектора Mx'_i, конец которого лежит на отрезке [Mn_j, Mn_k]. В силу линейной зависимости Mx'_i и Mn_j, Mn_k, имеем, что Mx'_i = (p / r)Mn_j + (q / r)Mn_k, где p + q = r и p, q, r — целые неотрицательные числа. Это эквивалентно rMx'_i = pMn_j + qMn_k, а значит, если на каждые r ходов Макса в Mx_i мы будем отвечать p ходами Мина в Mn_j и q ходами Мина в Mn_k, то суммарный сдвиг составит  - pMn_j - qMn_k + rMx_i =  - rMx'_i + rMx_i =  - r(Mx'_i - Mx_i), то есть вектор со строго отрицательными компонентами. Таким образом, мы можем мажорировать данный ход Макса, т. е. он ему невыгоден.

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

Либо этот ход пересекает выпуклую оболочку, но выходит из неё наружу — в таком случае этот ход Макса не короче всех ходов Мина в некотором неотрицательном направлении, а значит Макс победил.

Либо же, вектор Макса находится сбоку от выпуклой оболочки ходов Мина. Пусть для определённости вектор Mx_i В таком случае, требуется отдельный анализ. Рассмотрим самый верхний из векторов Мина. Если вектор Mx_i не ниже самого верхнего из ходов Макса Mx_j, то по первому утверждению Макс может выиграть, ходя исключительно в этот вектор. В противном же случае, как несложно видеть, разность Mn_i - Mx_j — это вектор со строго отрицательными компонентами, ходя в который мы можем мажорировать соответствующий вектор Макса.

Значит, полная версия критерия победы Мина выглядит следующим образом. Рассмотрим выпуклую оболочку ходов Мина и продлим её от самой верхней точки влево и от самой правой точки вниз. Если все ходы Макса попадают строго внутрь образованной фигуры, то Мин побеждает. Иначе побеждает Макс.

562F - Подбор имён

(в трансляции: 566A - Подбор имён)

Сформиурем бор из всех имён и псевдонимов. Отметим красным все вершины, соответствующие именам, и синим все вершины, соответствующие всем псевдонимам (одна вершина может быть отмечена несколько раз, в том числе разными цветами). Заметим, что если мы сопоставили имя a и псевдоним b, то качество такого сопоставления может быть выражено как lcp(a, b) = 1 / 2(2 * lcp(a, b)) = 1 / 2(|a| + |b| - (|a| - lcp(a, b)) - (|b| - lcp(a, b))), что представляет собой константу 1 / 2(|a| + |b|), из которой вычитается половина длины пути между a и b по бору. Таким образом, мы должны соединить все красные вершины с синими, минимизировав суммарную длину путей.

Нетрудно видеть, что такая задача решается жадным образом следующей рекурсивной процедурой: если у нас есть вершина v, в поддереве которой x красных вершин и y синих вершин, то мы должны сопоставить min(x, y) красных вершин этого поддерева синим вершинам, а оставшиеся max(x, y) - min(x, y) красных или синих вершин "отдать" на уровень выше. Корректность данного алгоритма легко объясняется следующим соображением. Ориентируем ребро каждого пути по направлению от красной вершины к синей. Если ребро получает две разных ориентации, то два пути, на которых оно лежит, легко "развести", уменьшив их суммарную длину.

Таким образом, получается несложное решение за O(sumlen), где sumlen — суммарная длина всех имён и псевдонимов.

562G - Репликация процессов

(в трансляции: 566B - Репликация процессов)

Эту задачу можно решить симулируя процесс реплицирования. Будем к каждому шагу поддерживать список всех репликаций, которые в текущий момент можно применить. Применяем любую репликацию, после чего обновляем список, добавляя/удаляя все подходящие или переставшие быть подходящими репликации со всех затронутых на данном шаге серверов. Список репликаций можно поддерживать в структуре данных "двусвязный список", которая позволяет за O(1) добавлять и удалять элемент в/из множества и вынимаь произвольный элемент множества.

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

Получается решение за O(n) операций (впрочем, константа, скрытая за O-нотацией весьма немаленькая — один только ввод составляет 12n чисел, да и само решение оперирует по меньшей мере константой 36).

Мы были вынуждены удалить регистрации, сделанные до 00:00, так как регистрационная форма на тот момент не поддерживала регистрацию команд. Пожалуйста, пройдите регистрацию вновь, если ваша регистрация была удалена.

Вчера завершился финал чемпионата VK Cup 2015, о котором вы могли прочитать в предыдущих наших постах. Осталось объявить последнее событие, связанное с прошедшим чемпионатом — онлайн-трансляцию, которая состоится в четверг 30 июля в 19:00 по Москве. К соревнованию допускаются как индивидуальные участники, так и команды из двух человек, которые желают почувствовать себя участниками финала соревнования. Трансляция продлится три часа, задачи будут перемешаны по сравнению с оригинальным порядком. Допускаются участники обоих дивизионом, но мы считаем своим долгом предупредить, что для участников из второго дивизиона набор задач, скорее всего, будет слишком сложным. Этот раунд является рейтинговым раундом Codeforces.

В заключение мы хотели бы поблагодарить всех людей, которые помогли чемпионату состояться. Придумывали и готовили задачи для вас сотрудники ВКонтакте, члены команды Codeforces и другие люди, любезно предложившие свою помощь: PavelKunyavskiy, burunduk3, Dmitry_Egorov, Kurpilyansky, dark_ai, MikeMirzayanov, Zlobober, MaximShipko, kuviman, Nickolas, Errichto, sankear и malcolm. Хочется сказать большое спасибо людям, прорешивавшим наши раунды, и дававшим ценные советы по поводу задач: winger и AlexFetisov. Также, мы благодарим всех работников ВКонтакте, с которыми вместе мы занимались проведением чемпионата: burunduk3, Burunduk2, KOTEHOK и многих других. Спасибо!

Всем удачи на онлайн-трансляции!

UPD: Обратите внимание, что во время раунда команде разрешается пользоваться только одним компьютером. Это значит, что программировать/пользоваться консолью/как-либо иначе продвигаться в решении задач в один момент времени можно только с одного компьютера. Единственное, что разрешается делать с двух компьютеров — это читать условия.

UPD2: Так как это командное соревнование, специально для вашего удобства мы выкладываем запароленный архив с pdf-условиями задач: vkcup2015-mirror-statements.zip. С началом тура мы опубликуем пароль к нему.

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

UPD4: По техническим причинам начало раунда переносится на 19:20 по Москве.

UPD5: Пароль на архив с условиями: vkcup4ever. Удачи!

UPD6: Онлайн-трансляция завершена! Поздравляем победителей:

1. rng_58
2. Zenith: I_love_Hoang_Yen, ngfam_kongu
3. OrOrZZZ!: zld3794955, KFDong
4. Petr team: Petr, ilyakor
5. jcvb_matthew99: matthew99, jcvb

Мой персональный респектам команде Petr team: Petr, ilyakor за единственное решение по задаче Е в трансляции, пользователю rng_58 и команде Excited: YuukaKazami, jqdai0815 за два правильных решения по задаче С.

Также, поздравляем пользователя rng_58, который продемонстрировал, что одиночному пользователю есть что противопоставить командам, состоящим из двух людей!

Рейтинг будет пересчитан в ближайшее время.

UPD7: Разбор!

Всем привет!

Вчера, 24 июля, мы открыли финал VK Cup 2015! В течение дня к нам съехались все участники финала соревнования, а те из них, кто прибыл пораньше, успели насладиться прогулкой по крышам Санкт-Петербурга. А сегодня через пару часов состоится пробный тур, во время которого участники смогут познакомиться с условиями проведения финала и попробовать свои силы в решении пары обычных (и не совсем) задач. После обеда участников ждёт первый тур нашего соревнования, CodeGame Coding, в рамках которого им предстоит написать стратегию для управления боевым магом.

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

Результаты пробного тура будут доступны для болельщиков по данному адресу. Ждите новостей от нас!

Round #309 was first moved from Monday to Tuesday, and now it is moved to Wednesday because of our technical reasons and schedule of other online contests. Don't be confused with that. Stay tuned!

Google Code Jam Distributed Round starts in 15 minutes. It's a brand new format of contest, top-10 will advance to its own onsite final round in Seattle.

Let's discuss problems here after round finishes.

GL & HF everybody!

Сегодня в 17:00 по Москве начинается третий раунд Google Code Jam, топ-25 участников которого отправятся на финал соревнования в Сиэтл. Всем удачи!

Introduction

Checker is a program that should be written when task allows more than one correct solution. Although it seems that it is very easy to write checker, there are lots of important technical details that are easy to forget if you don't use a special library like testlib.h.

A common convention is that a checker should be a program taking three command-line arguments: the testdata filename, the participant output filename and the jury answer filename. Checker should read the contents of the input, output and answer, decide whether participant answer is correct (and optimal being compared to the jury's answer if there can be unoptimal answer in this task) and return one of several pre-defined verdicts:

Usually the verdict returned by checker is indicated by the return code of its executable, but it may possibly be transfered to the testing system by many other ways: by creating a special xml-file with checker outcome, by writing to stdout or somehow else. When using testlib.h for writing a checker all those system-dependent ways are combined in a single expression quitf(VERDICT, "comment", ...).

Simplest checker example

Problem statement: You are given two integers a and b ( - 1000 ≤ a, b ≤ 1000). Find their sum and output it.

Let's write a checker for this problem. It will be very simple:

#include "testlib.h"

int main(int argc, char* argv[]) {
    // This command initializes checker environment.
    registerTestlibCmd(argc, argv);
    // Now there are three global variables specifying testlib streams:
    // inf - stream with the testdata.
    // ouf - stream with the contestant output.
    // ans - stream with the jury answer.
    // All those streams provide the similar interface for reading data.

    // This function reads a single integer from the participant output that 
    // should be between -2000 and 2000. If it doesn't belong to the specified
    // range, checker finishes with verdict _pe and comment saying that [sum of numbers]
    // is outside of the specified range.
    int pans = ouf.readInt(-2000, 2000, "sum of numbers");
    
    // This function reads a single integer from the jury output. Here we suppose
    // that jury's answer is correct and we do not need to additionally verify it.
    int jans = ans.readInt(); // We suppose that jury's answer is correct
    
    if (pans == jans)
        quitf(_ok, "The sum is correct."); // This finishes checker with verdit OK.
    else
        // quitf handles a comment like printf, i. e. you may use specifiers like
        // %d, %s etc in the comment.
        quitf(_wa, "The sum is wrong: expected = %d, found = %d", jans, pans);
}

Available methods

There are lots of methods useful for writing checkers.

TODO: finish this list.

readAns paradigm

Suppose you have a task that asks contestant to find a complex composite answer that is not just a single number. Example:

Problem statement You are given a connected undirected weighted graph witn n vertices and m edges. Find a simple path between vertex s and vertex t (s ≠ t) of maximum weight and output it. Samples (input and output format is clarified in square brackets):

Here is an example of bad checker implementation for this task.

Bad checker implementation

#include "testlib.h"
#include <map>
#include <vector>
using namespace std;

map<pair<int, int>, int> edges;

int main(int argc, char* argv[]) {
    registerTestlibCmd(argc, argv);
    int n = inf.readInt(); // no need to additionally call readSpace() or readEoln() since
    int m = inf.readInt(); // there is no need to validate input file in the checker
    for (int i = 0; i < m; i++) {
        int a = inf.readInt();
        int b = inf.readInt();
        int w = inf.readInt();
        edges[make_pair(a, b)] = edges[make_pair(b, a)] = w;
    }
    int s = inf.readInt();
    int t = inf.readInt();

    // reading jury answer
    int jvalue = 0;
    vector<int> jpath;
    int jlen = ans.readInt();
    for (int i = 0; i < jlen; i++) {
        jpath.push_back(ans.readInt());
    }
    for (int i = 0; i < jlen - 1; i++) {
        jvalue += edges[make_pair(jpath[i], jpath[i + 1])];
    }
    
    // reading participant answer
    int pvalue = 0;
    vector<int> ppath;
    vector<bool> used(n, false);
    int plen = ouf.readInt(2, n, "number of vertices"); // path should at least contain s and t
    for (int i = 0; i < plen; i++) {
        int v = ouf.readInt(1, n, format("path[%d]", i + 1).c_str());
        if (used[v - 1]) // checking that no vertex is used twice
            quitf(_wa, "vertex %d was used twice", v);
        used[v - 1] = true;
        ppath.push_back(v);
    }
    // checking that path is actually between s and t
    if (ppath.front() != s) 
        quitf(_wa, "path doesn't start in s: expected s = %d, found %d", s, ppath.front());
    if (ppath.back() != t)
        quitf(_wa, "path doesn't finish in t: expected t = %d, found %d", t, ppath.back());
    // checking that each pair of adjacent vertices in the path is indeed connected by an edge
    for (int i = 0; i < plen - 1; i++) {
        if (edges.find(make_pair(ppath[i], ppath[i + 1])) == edges.end())
            quitf(_wa, "there is no edge (%d, %d) in the graph", ppath[i], ppath[i + 1]);
        pvalue += edges[make_pair(ppath[i], ppath[i + 1])];
    }
    
    if (jvalue != pvalue)
        quitf(_wa, "jury has answer %d, participant has answer %d", jvalue, pvalue);
    else
        quitf(_ok, "answer = %d", pvalue);
}

Here are the main two issues that appear in this checker.

1. It believes that the jury's answer is absolutely correct. In case when jury's answer is unoptimal and contestant have really found the better answer, he will get the verdict WA that is not fair. There is a special verdict Fail exactly for this situation.
2. It contains the duplicating code for extracting the answer value for jury and contestant. In this case extracting the value is just one "for" cycle but for a harder task it may be a very complicated subroutine, and as usual, using the duplicated code makes twice harder to fix it, rewrite it or change it when output format changes.

In fact, reading an answer value is a subroutine that works exactly the same for contestant and jury. That's why it is usually being put into a separate function receiving the input stream as a parameter.

Good checker implementation

#include "testlib.h"
#include <map>
#include <vector>
using namespace std;

map<pair<int, int>, int> edges;
int n, m, s, t;

// This function receives stream as an argument, reads an answer from it,
// checks its correctness (i. e. that it is indeed a correct path from s to t in the graph),
// calculates its value and returns it. If the path is incorrect, it stops the execution
// with _wa outcome if stream = ouf (contestant) or with _fail outcome if stream = ans (jury).
int readAns(InStream& stream) {
// reading participant answer
    int value = 0;
    vector<int> path;
    vector<bool> used(n, false);
    int len = stream.readInt(2, n, "number of vertices"); // path should at least contain s and t
    for (int i = 0; i < len; i++) {
        int v = stream.readInt(1, n, format("path[%d]", i + 1).c_str());
        if (used[v - 1]) { // checking that no vertex is used twice
            // stream.quitf works as quitf but it modifies the verdict according
            // to what stream it is being invoked from. If stream == ouf then
            // it works exactly like quitf, otherwise if stream == ans then
            // any verdict will work like _fail (because it's bad when jury's answer is incorrect)
            stream.quitf(_wa, "vertex %d was used twice", v);
        }
        used[v - 1] = true;
        path.push_back(v);
    }
    // checking that path is actually between s and t
    if (path.front() != s) 
        stream.quitf(_wa, "path doesn't start in s: expected s = %d, found %d", s, path.front());
    if (path.back() != t)
        stream.quitf(_wa, "path doesn't finish in t: expected t = %d, found %d", t, path.back());
    // checking that each pair of adjacent vertices in the path is indeed connected by an edge
    for (int i = 0; i < len - 1; i++) {
        if (edges.find(make_pair(path[i], path[i + 1])) == edges.end())
            stream.quitf(_wa, "there is no edge (%d, %d) in the graph", path[i], path[i + 1]);
        value += edges[make_pair(path[i], path[i + 1])];
    }
    return value;
}

int main(int argc, char* argv[]) {
    registerTestlibCmd(argc, argv);
    n = inf.readInt(); // no need to additionally call readSpace() or readEoln() since
    m = inf.readInt(); // there is no need to validate input file in the checker
    for (int i = 0; i < m; i++) {
        int a = inf.readInt();
        int b = inf.readInt();
        int w = inf.readInt();
        edges[make_pair(a, b)] = edges[make_pair(b, a)] = w;
    }
    int s = inf.readInt();
    int t = inf.readInt();

    int jans = readAns(ans);
    int pans = readAns(ouf);
    if (jans > pans)
        quitf(_wa, "jury has the better answer: jans = %d, pans = %d\n", jans, pans);
    else if (jans == pans)
        quitf(_ok, "answer = %d\n", pans);
    else // (jans < pans)
        quitf(_fail, ":( participant has the better answer: jans = %d, pans = %d\n", jans, pans);
}

Notice that by using this paradigm we also check the jury answer for being correct. Checkers written in such form are usually shorter and easier to understand and fix. It is also applicable when task output is NO/(YES+certificate).

Notes, advices and common mistakes

• Use readAns paradigm. It really makes easier to understand and work with your checker.
• Always use optional arguments for methods like readInt(), readLong() etc. If you forget to check range for some variable, your checker may work incorrectly or even face runtime-error that will result in Check Failed in testing system.

Bad:

// ....
int k = ouf.readInt();
vector<int> lst;
for (int i = 0; i < k; i++)       // This will behave similarly for k = 0 as well as for k = -5.
    lst.push_back(ouf.readInt()); // But we don't want to accept list of length -5, don't we?
// ....
int pos = ouf.readInt();
int x = A[pos]; // 100% place for runtime-error. There will surely be a contestant who will output
                // -42, 2147483456 or some other garbage instead of correct value.
// ....

Good:

// ....
int k = ouf.readInt(0, n); // Now negative values of k will cause PE.
vector<int> lst;
for (int i = 0; i < k; i++)
    lst.push_back(ouf.readInt());
// ....
int pos = ouf.readInt(0, (int)A.size() - 1); // That's how we prevent index out of range.
int x = A[pos]; 
// ....

• Use optional comments in readXXX methods. With them it is much easier to understand where did checker stop its execution (if not you don't specify it, the comment will be like "integer doesn't belong to range [23, 45]" and it's not clear what integer caused such behavior). Also write informative comments in quitf calls; remember that your comments will be probably available to the contestants after the competition (or even during the competition like while hacking on Codeforces).

542A - Здесь могла быть ваша реклама

Зафиксируем окно на телеканале и поймём, какой ролик имеет с ним наибольшее пересечение. Ролики бывают четырёх видов: вкладывающиеся в окно, накрывающие окно, частично пересекающие его слева и частично пересекающие справа. Научимся разбирать каждый вид.

Определить наличие накрывающего ролика просто — достаточно отсортировать ролики в порядке возрастания левой границы, и, идя по ним слева направо, поддерживать минимальную правую границу, достигнутую к текущему моменту. Если, проходя через окно j, мы видим, что текущее значение максимума не меньше, чем b_j, то есть ролик, накрывающий наше окно, а значит ответ для данного окна можно установить равным (r_i - l_i)·c_i.

Среди всех вкладывающихся роликов надо найти тот, который имеет максимальную длину. Это можно сделать похожим образом, но чуть-чуть сложнее. Воспользуемся методом сканирующей прямой. Проходя через правую границу ролика r_i, будем присваивать в некоторой структуре данных (например, дереве отрезков), значение r_i - l_i в точку l_i. Проходя через правую границу окна, будем считать ответ для него как максимум на отрезке [a_j, b_j]. Таким образом мы учтём вложенные ролики.

Также можно определить наличие частично накрывающего ролика слева. Проходя через правую границу ролика r_i, будем писать в точку l_i значение r_i. Проходя через правую границу телеканала b_j, посчитаем для него ответ как максимум на отрезке [a_j, b_j] минус a_j.

Среди всех ответов для всех роликов выберем наиболее выгодный. Таким образом, выходит решение за .

Упражнение А если веса есть не только на окнах, но и на роликах, и они перемножаются? Решите задачу за , получите виртуальную медаль!

542B - Охота на уток

Будем приближаться к решению задачи постепенно. Во-первых, скажем, что у нас утки неподвижны, а охотник топает вправо со скоростью 1. Определим величину F[x][s] как минимальное количество уток среди тех, правые концы которых расположены не позже x, которых мы не сможем подстрелить, если последний выстрел был сделан ровно в точку s. В частности, в величину F[x][s] включены все утки, расположенные в отрезке [s + 1, x]. Значения F[x][s] для s > x будем считать неопределёнными.

Будем смотреть на F[x] как на функцию от s. Эта функция определена на всех s от 0 до x включительно. Ключевая идея заключается в исследовании того, как отличается F[x + 1][·] от F[x][·].

Давайте сначала предположим, что если в точке x + 1 не заканчивается ни одна утка, то в определении F[x + 1][·] фигурируют те же самые утки, что и в определении F[x][·]. Это значит, что все значения F[x][s] для s ≤ x остаются теми же. Интереснее дело обстоит с F[x + 1][x + 1]. Нетрудно видеть, что выстрел в точку x + 1 не может подбить ни одну из уток, заканчивающихся не правее x + 1 (так как мы только что предположили, что таких уток нет). Значит, F[x + 1][x + 1] = min F[x + 1][0... x + 1 - r] = min F[x][0... x + 1 - r].

Теперь давайте предположим, что в точке x + 1 заканчивается утка [l, x + 1]. В таком случае, можно смело сказать, что ко всем значениям D[x + 1][0... l - 1] можно прибавить 1 (потому что к моменту выстрела в точку s < l утку [l, x + 1] подбить ещё никак не возможно). В то же время, все значения D[x + 1][l... x + 1] останутся прежними, потому как последний выстрел и подобьёт новодобавленную утку.

Теперь давайте постепенно понимать реализационную сторону вопроса. Функция F[x][·] является кусочно-постоянной, а значит, её можно хранить в декартовом дереве в виде набора пар (начало отрезка, значение на отрезке). Такое хранение позволит нам легко прибавлять 1 на отрезке и брать минимум на префиксе функции.

Теперь будем считать, что функция F[x][·], определена на всей положительной полуоси, просто значения F[x][s] для s > x не удовлетворяют определению функции F[x][s]. Можно мысленно представить, что последний отрезок в структуре F[x] просто продляется до бесконечности вправо.

Будем идти сканирующей прямой по переменной x. Заметим, что функция F[x + 1][·] по сравнению с функцией F[x][·] меняется очень редко. Например, значение F[x + 1][x + 1] практически всегда совпадает с F[x][x + 1] (которое, в свою очередь, совпадает с F[x][x], о чём сказано абзацем выше). Действительно, в предположении, что в x + 1 не заканчивается ни одна утка, F[x][x] = min(F[x][0... x - r]) и F[x + 1][x + 1] = min(F[x + 1][0... x + 1 - r]) = min(F[x][0... x + 1 - r]) ≤ min(F[x][0... x - r]). Таким образом, интересное для нас событие возникает, когда значение F[x][x - r + 1] меньше всего префикса перед ним. Однако, величина min(F[x][0... x - r]) может не более n раз увеличиться на 1 (каждый раз, когда x проходит через правый конец утки), а значит, и уменьшиться может не более n раз (так как это неотрицательная величина).

Значит, событий вида "мы прошли через правый конец утки" и "нам надо нетривиально посчитать F[x][x] в сумме линейное количество. Каждое из них обрабатывается с помощью обращения к декартову дереву, которое происходит за . А значит, мы получили решение, работающее за . Ура!

542C - Идемпотентная функция

Для решения этой задачи полезно разобраться, как выглядит граф, отвечающий функции из множества {1, ..., n} в себя. Рассмотрим граф на вершинах 1, ..., n, где из вершины i ведёт ребро в вершину f(i). Такой граф всегда выглядит как набор циклов, в которые ведут деревья. Как же должен выглядеть граф, отвечающий инволюции? Нетрудно понять, что в таком графе все циклы должны быть длины 1, а все вершины, которые не являются циклами длины 1 (т. е. неподвижными точками), должны сразу вести в какую-то неподвижную точку.

Значит, мы должны соблюсти два условия. Во-первых, все циклы должны стать длины 1 — для этого, как нетрудно понять, k должно делиться на [c₁, c₂, ..., c_m], где c_i — длины всех циклов. Во-вторых, все вершины, не лежащие на циклах, должны стать переходящими в вершины, лежащие на циклах. Иными словами, k должно быть не меньше, чем расстояние от любой вершины x до цикла, в которую она попадает (или, что то же самое, длины предпериода в последовательности f(x), f(f(x)), f(f(f(x))), ...).

Значит, наша задача свелась к тому, чтобы найти минимальное число k, делящееся на A, и не меньшее, чем B, что совсем несложно сделать.

Упражнение Какой максимальный ответ достигается в этой задаче? (Ответ: раз два)

542D - Супергеройская работа

Первым делом в этой задаче стоит разобраться, что из себя представляет функция Джокера. Одним из главных её свойств является мультипликативность: J(ab) = J(a)J(b) для (a, b) = 1, что даёт нам возможность записать значение функции, зная её значение на простых множителях аргумента: J(p₁^k₁p₂^k₂... p_m^k_m) = J(p₁^k₁)J(p₂^k₂)... J(p_m^k_m) = (p₁^k₁ + 1)(p₂^k₂ + 1)... (p_m^k_m + 1). Воспользуемся этим знанием, чтобы решить задачу методом динамического программирования.

Обозначим за P множество тех простых чисел p, что скобка с их участием может встретиться в A = J(x). Таких простых немного — для каждого делителя d числа A он может соответствовать не более, чем одному простому, а именно, тому, чьей степенью является число d - 1 (если вообще является). Составим множество P, запомнив также для каждого простого числа p в нём, в каких степенях k скобка (p^k + 1) делит A.

Теперь можно посчитать величину D[p][d], которая равна количеству способов получить делитель d числа A в виде произведения скобок от первых p простых чисел в множестве P. Такую величину можно посчитать методом динамического программирования за , где — количество делителей числа A (так как выше было показано, что ). Значит, общая сложность решения — .

Упражнение Как себя ведёт с ростом A? Например, какое максимальное значение по всем A ≤ 10¹²? (Ответ: . Полезная оценка, не являющаяся, тем не менее, точной асимптотикой, заключается в том, что )

Упражнение А какой максимальный ответ достигается в этой задаче? Если получится сгенерировать тест, в котором ответ больше миллиона, с меня большой респект!

542E - Игра на графе

Заметим, что если исходный граф — недвудольный, то ответ — (-1). Действительно, любой нечётный цикл, будучи стянутым по паре вершин, всегда порождает нечётный цикл меньшего размера, в результате чего мы получим треугольник, с которым уже никак справиться нельзя.

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

Последним шагом остаётся заметить, что ответ — сумма ответов для отдельных компонент, которые можно по очереди подцепить друг другу. Таким образом, ответ — сумма диаметров компонент связности, если они все двудольные, иначе — (-1). Решение имеет сложность O(E + VE) (первое слагаемое — проверка на двудольность, второе слагаемое — подсчёт диаметра путём запуска BFS из каждой компоненты связности).

542F - Квест

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

Будем идти по дереву снизу вверх. Посчитаем величину D[h][c] — максимальная возможная стоимость, которую можно получить, если, находясь на уровне h, мы имеем c вершин. Для перехода переберём, сколько листов именно имеющейся глубины мы возьмём (понятно, что из них выгоднее всего взять несколько максимальных), пусть, мы возьмём k. Тогда из этого состояния можно сделать переход в состояние D[h - 1][⌈(c + k) / 2⌉]. Ответ будет находиться в величине D[0][1] — действительно, придя на глубину 0, мы должны остаться с одной-единственной вершиной — корнем.

Сложность решения — O(n²T).

Упражнение Прокачайте решение выше до . А потом до

В воскресенье, 3-го мая, в 19:00 начнётся Раунд 3 чемпионата по программированию VK Cup 2015! Не забудьте зарегистрировать вашу команду на раунд, регистрация закроется за пять минут до его старта.

В этом раунде могут принять участие все те команды, которые отобрались в Раунде 2 или в Уайлд-кард раунде 2. Напомним, что из второго раунда допущены все те команды, что набрали не менее 928 баллов. В уайлд-кард раунде 2 было достаточно набрать 1827 баллов. Таким образом, принять участие в Раунде 2 могут 100 + 20 = 120 команд!

Участников ждет соревнование по правилам классических раундов Codeforces. Раунд 3 пройдёт в таком же формате, как и Раунд 2 — с онлайн-трансляцией, рейтинговой и доступной только для див-1 участников. Будет использована плавная динамическая система оценки задач, но сами задачи будут расположены в случайном порядке. Участникам будет предложено 6 задач.

Раунд подготовлен силами команды Codeforces, команды VK и пользователя yeputons. Как всегда, неоценимую помощь в тестировании задач оказали winger и AlexFetisov.

Напомним, что в Финал VK Cup пройдут все те команды, которые наберут положительный балл, не меньший, чем у команды на 20-м месте. Также обращаем ваше внимание, что участники всех команд, прошедших в Раунд 3 (независимо от их участия или неучастия в Раунде 3 или в его трансляции), получат фирменную футболку Чемпионата. Помимо этого, фирменной футболкой будут награждены топ-50 участников интернет-трансляции Раунда 3.

Желаем удачи и интересной борьбы!

UPD1 Раунд 3 завершён! Поздравляем топ-20 команд, которые отправятся в июле на Финал VK Cup 2015! Следите за объявлениями на сайте, точная информация о финальном раунде появится позднее.

UPD2 Тем временем появился разбор.

532A - Шахтёры Берляндии

Доступна только английская версия разбора в английской версии поста.

532B - Рабочая группа

Эту задачу можно решить с помощью динамического программирования по поддеревьям иерархии сотрудников. Обозначим за D[v][e] максимальную эффективность, которую можно получить, взяв некоторое количество сотрудников из поддерева человека v, таким образом, чтобы их количество имело чётность e, и условие задачи выполнялось для всех взятых людей. Тогда нетрудно пересчитать D[v][e] через детей вершины v с помощью подсчёта промежуточной величины T[i][e] — максимальной эффективности, которой можно достичь, пройдя первые i поддеревьев вершины v, если чётность количества взятых людей — e.

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

532C - Игра на доске

Рассмотрим три случая.

1) x_p  +  y_p ≤  max(x_v,  y_v). В этом случае Поликарп может оказаться в (0,  0) через x_p  +  y_p ходов и Василий всегда будет "позади". Для Поликарпа достаточно делать любой возможный ход, и это приведёт его к победе. Нетрудно это объяснить тем, что условие x_p  +  y_p ≤  max(x_v,  y_v) будет выполнено и после любых возможных ходов Поликарпа и Василия. Иными словами, Василий просто не может победить.

2) x_p ≤ x_v, $y_p \leq y_v$. В этом случае Поликарп должен некоторым образом блокировать Василия. Он должен совершать такой ход, чтобы после любого возможного хода Василия неравенство было снова выполнено.

• Если x_p  =  x_v  >  0, нужно пойти в (xp  -  1,  yp).
• Если yp  =  yv  >  0, нужно пойти в (xp,  yp  -  1).
• В противном случае можно совершить любой допустимый ход.

Действуя по такой стратегии, мы снова не даём Василию возможности выиграть.

3) В противном случае рассмотрим любой кратчайший путь для Василия до точки (0,  0). Любая клетка этого пути ближе к Василию, чем к Поликарпу, поэтому Поликарп никак не может помешать Василию на этом пути. А значит, Василий дойдёт до финиша первым. Альтернативное объяснение заключается в том, что Василий всегда может сходить таким образом, чтобы ни одно из условий 1) и 2) не оказалось выполненным.

532D - Колонны

Первое наблюдение: колонна рушится только если расстояние между её соседями больше, чем 2d_i, поэтому для неё не имеет значения, где именно она находится на отрезке между своими соседками. Важно только расстояние между ними.

Для каждой колонны C давайте определим, существует ли набор колонн слева такой, что слева от C всё устойчиво. Если ответ да, то тогда давайте определим, как близко может находиться ближайшая к C слева в этом наборе колонна. Зная это, мы узнаем, как далеко справа может находиться следующая за C колонна. Воспользуемся динамическим программированием.

Медленный подход: для каждой предыдущей колонны проверим, может ли она быть соседом C. Ближайшая колонна, которая может, является будет тем самым левым соседом C.

Более быстрый подход: давайте обозначим за far[i] наибольшую возможную координату, где может находиться правый сосед колонны i. В нашей динамике заведём стек с возможными кандидатами на то, чтобы быть левым соседом каждой колонны. В этом стеке колонны будем поддерживать в порядке возрастания индекса (а, значит, и координаты) и одновременно в порядке убывания far[i] (действительно, нам незачем хранить в стеке колонну, если её мажорирует и по координате, и по far[i] какая-то другая колонна).

Теперь для каждой новой колонн мы должны удалить с вершины стека некоторое количество колонн со слишком малым значением far[i]. Последняя оставшаяся колонна на стеке будет той самой, через которую мы пересчитаем значение нашей динамики. Эта часть занимает O(n) времени.

Если существует колонна с far[i] не меньше координаты правой несущей колонны, то ответ--- 0, так как конструкция исходно устойчива.

Теперь посчитаем ту же самую величину справа налево. Теперь некоторые колонны связаны с левой несущей, некоторые — с правой. Мы хотим поставить новую так, чтобы попасть в пределы far[i] как для левой колонны, так и для правой. Это можно сделать, используя технику двух указателей по двум образованным стекам.

Описанное решение работает за O(n) времени и памяти.

532E - Исправление ошибок

Предположим для определённости, что S получается из W удалением более раннего символа, чем T. Тогда W  =  A  +  x  +  B  +  y  +  C, S  =  A  +  x  +  B  +  C, T  =  A  +  B  +  y  +  C, где x и y — удаляемые символы, а A, B и C — какие-то (возможно, пустые) строки.

Определим A как наибольший общий префикс S и T, а C — как наибольший общий суффикс. Удалим их из обоих строк. Теперь мы знаем буквы x и y — это соответственно первая буква строки S и последняя буква строки T. Удалим и их тоже. Остаётся лишь проверить, равны ли оставшиеся части строк.

Проделаем так для S и T, а также для T и S.

532F - Кодирование

У этой задачи возможно два направления решения.

Зафиксируем пару букв x и y. Заменим в строке S все буквы x на единицы, а все остальные буквы на нули. В строке T заменим все буквы y на единицы, а все остальные буквы на нули. С помощью алгоритма КМП или Z-функции определим все позиции, в которых строку T можно приложить к строке S так, что они совпадут. Если такое условие выполнено как для пары букв (x, y), так и для пары букв (y, x), то это значит, что в данной позиции можно приложить T к S с заменой x <-> y и возможно ещё какими-то заменами.

Теперь для каждой позиции надо проверить, разбиваются ли буквы на пары в соответствии с известной нам информацией. Это можно сделать за O(sigma), где sigma  =  26 — размер алфавита. Таким образом, решение работает за O(n  *  sigma2  +  n  *  sigma)  =  O(n  *  sigma2). Это решение при должной аккуратности реализации проходит по времени.

Другой способ — произвести замену, которая позволит нам сравнивать строки с точностью до переименовывания букв. Заменим каждую букву на расстояние до предыдущей такой же в обоих строках. Теперь для совпадения с точностью до переименования достаточно проверить, что строка T совпадает с подстрокой строки S во всех позициях кроме, возможно первых вхождений каждой буквы в T. Это можно сделать с помощью модифицированной префикс-функции или хеширования.

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

В пятницу, 17-го апреля, в 19:00 начнётся Раунд 2 чемпионата по программированию VK Cup 2015! Не забудьте зарегистрировать вашу команду на раунд, регистрация закроется за пять минут до его старта.

В этом раунде могут принять участие все те команды, которые отобрались в Раунде 1 или в Уайлд-кард раунде 1. Напомним, что из первого раунда допущены все те команды, что набрали не менее 796 баллов. В уайлд-кард раунде было достаточно решить не менее шести задач, либо решить пять задач со штрафным временем не более 415 минут. Таким образом, принять участие в Раунде 2 могут 400 + 50 = 450 команд!

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

Во-вторых, вас, как и ранее, ждёт плавная динамическая система оценки задач, но сами задачи будут расположены в случайном порядке. Участникам будет предложено 6 задач.

Раунд подготовлен силами команды Codeforces, команды VK и пользователя Errichto, который предложил свою неоценимую помощь в рамках кампании "5 лет Codeforces". Большую помощь в тестировании задач оказал winger.

Напомним, что в Раунд 3 пройдут все те команды, которые наберут положительный балл, не меньший, чем у команды на 100-м месте. Также обращаем ваше внимание, что все команды, проходящие в Раунд 3, получат фирменную футболку Чемпионата. Помимо этого, фирменной футболкой будут награждены топ-50 участников интернет-трансляции Раунда 3.

Желаем удачи и интересной борьбы!

UPD: Благодарим всех за участие! Появился разбор задач. Ждём вас на Уайлд-кард раунде 2 и Раунде 3!

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

524A - Возможно, вы знаете этих людей?

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

Тонкий момент №1: несмотря на то, пар друзей во вводе не более 100, самих людей может быть до 200, и можно ошибиться в выставлении размеров массивов.

Тонкий момент №2: нужно аккуратно сравнивать вещественные числа. Если написать нечто вроде common / degree >= k / 100.0, то в силу специфики вычислений с вещественными числами, результат такой проверки может быть недетерминирован (если в какую-то из частей внесётся незначительная погрешность). Поэтому, надо либо сравнивать с точностью до некоторого eps, либо выполнять проверку в целых числах: common * 100 >= degree * k.

524B - Фото на память - 2 (round version)

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

529B - Фото на память - 2 (online mirror version)

В версии для онлайн-трансляции условие было незначительно изменено — разрешается, чтобы не более n / 2 людей лежали на фотографии. Это слегка усложняет решение. Введём терминологию: людей, у которых w ≤ h, будем называть высокими, а остальных людей — широкими. Зафиксируем итоговую высоту фотографии H. Далее, следует небольшой разбор случаев.

• Если высокий человек влезает под высоту H, то мы его оставляем именно в таком состоянии.
• Если высокий человек не влезает под высоту H, то мы обязаны его положить, увеличиваем счётчик таких людей на 1.
• Если широкий человек влезает под высоту H, но не влезает, будучи положенным, то ставим его.
• Если широкий человек влезает под высоту H обоими способами, то сначала ставим его, а в отдельный массив выписываем величину, на которую уменьшится ответ, если этого человека всё-таки положить: w - h.
• Если же кто-то не влезает ни одним из двух способов, то подобное значение H недопустимо.

Теперь у нас есть какое-то количество людей, которые обязательно должны лечь (из второго пункта), причём, если их слишком много, а именно, больше, чем n / 2, то подобное значение H недопустимо.

За вычетом людей из второго пункта у нас осталось некоторое количество вакантных лежачих мест — распределяем их по людям из четвёртого пункта в порядке уменьшения величины (w — h). Считаем площадь фотографии, выбираем минимум по всем H.

524C - Искусство обращения с бакноматом

Предполагаемое решение имеет сложность или . Для каждой возможной суммы денег x = t·a_i (1 ≤ t ≤ k) выпишем пару (x, t) в массив, здесь t — количество купюр, которым такую сумму можно достичь. Отсортируем этот массив. Тогда чтобы ответить на один запрос, переберём первое слагаемое в сумме, а второе либо найдём бинарным поиском, либо воспользуемся методом двух указателей, чтобы найти парное слагаемое за амортизированное время O(1). Проверим, что получилось не более k купюр в сумме, улучшим ответ, если надо.

524D - Социальная сеть

Будем жадно действовать следующим образом. Идём по запросам в порядке поступления. Каждый очередной запрос пытаемся сопоставить новому человеку. Разумеется, это не всегда возможно сделать — если у нас уже есть M активных людей на сайте, то мы обязаны сопоставить очередной запрос кому-то из них. Возникает вопрос — кому именно?

Можно показать, что выгоднее всего сопоставить этот запрос самому недавнему из активных людей. Действительно, подобное “критическое” (по количеству людей) состояние можно задать вектором из M чисел — временами с момента последнего запроса каждого из людей в убывающем порядке. Тогда если сейчас состояние — (a₁, a₂, ..., a_M), то мы можем перейти в одно из M новых состояний (a₁, a₂, ..., a_M - 1, 0), (a₁, a₂, ..., a_M - 2, a_M, 0), ... , (a₂, a₃, ..., a_M, 0), в зависимости от того, к кому мы подцепим очередной запрос. Видно, что самый первый вектор покомпонентно больше, чем любой из оставшихся, а это значит, что он выгоднее всех остальных (т. к. чем больше число на определённой позиции в векторе, тем скорее может исчезнуть этот человек, и тем больше у нас остаётся свободы для последующих действий).

Значит, нам требуется моделировать процесс, поддерживая в некоторой структуре данных множество активных людей с временами их активности. В качестве подобной структуры можно воспользоваться любой структурой, реализующей интерфейс очереди с приоритетом (priority_queue, set, дерево отрезков или что-либо ещё). Итоговая сложность решения — .

524E - Ладьи и прямоугольники

Поймём, что означает тот факт, что какая-то клетка прямоугольника не побита ладьёй. Это значит, что существует строка прямоугольника, не содержащая ладью, и существует столбец прямоугольника, не содержащий ладью. Не очень ясно, как проверять это утверждение, поэтому проверим обратное к нему — мы только что показали, что прямоугольник является покрытым, если либо в каждой строке стоит ладья, либо в каждом столбце стоит ладья.

Эти утверждения можно проверять по отдельности. Как проверить для набора прямоугольников, что в каждой строке находится отмеченная точка? Это можно сделать за один проход вертикальной сканирующей прямой. Пусть мы идём слева направо и прошли через правую границу прямоугольника, расположенного в строках с a-й по b-ю, левая граница которого находится в столбце x. Тогда если обозначить за last[i] позицию последней ладьи, встреченной в строке номер i, то критерий для прямоугольника выглядит следующим образом: . Это значит, что для хранения величины last можно воспользоваться деревом отрезков. Аналогично проверяем для столбцов. Выходит решение, отвечающее на все запросы off-line за время O((q + k)log(n + m)).

524F - И снова правильная скобочная последовательность

Общая идея заключается в том, что скобочные последовательности можно рассматривать как последовательности балансов префиксов, т. е. как последовательности чисел (a_i), где a_i + 1 = a_i ± 1.

Посчитаем количество открывающихся скобок A и закрывающихся скобок B в исходной строке. Заметим, что если A >  = B, то строку всегда можно исправить, дописав A - B закрывающихся скобок в конец, и циклически сдвинув строку в точку минимума баланса, а если A ≤ B, то строку аналогично можно исправить, дописав B - A открывающихся скобок в начало. Очевидно, что меньшим количеством скобок не обойтись. Таким образом, мы уже знаем величину ответа, теперь нужно понять, как он устроен.

Будем считать, что мы сначала производим циклический сдвиг, а потом только добавляем скобки. Пусть, для определённости, мы дописываем x закрывающихся скобок. Сформулируем два несложных утверждения:

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

Каждое из этих утверждений несложно проверить, а в совокупности они нам дают тот факт, что в оптимальном ответе мы дописываем закрывающиеся скобки в конец строки. Значит, нам надо рассмотреть множество таких циклических сдвигов строки, что они превращаются в правильную скобочную последовательность при приписывании в конец x = A - B закрывающихся скобок (т. е. просто не имеют нигде отрицательного баланса), и выбрать из них лексикографически минимальный. Сравнение циклических сдвигов строки можно проводить либо при помощи суффиксного массива, либо же, так как нам требуется только найти минимальный сдвиг из определённого множества, можно сравнивать сдвиги между собой при помощи бинарного поиска и хеширования.

Аналогично делается случай, когда A ≤ B, с единственным отличием, что открывающиеся скобки дописываются в начало.

Таким образом, выходит решение за сложность .

527A - Игра с бумагой

It’s easy to see that described process is equivalent to the following loop:

while a > 0 and b > 0:
    if a ⩾ b:
         a = a - b
    else:
         b = b - a
    ans = ans + 1

But such naive approach will obviously lead to verdict TLE, since it makes ~10, 2015 - 03 - 19¹² operations even on the third sample test. The key idea is to replace repeating subtraction operations with integer division operations. This leads to the logarithmic-time solution that looks similar to the Euclid algorithm:

while a > 0 and b > 0:
    if a ⩾ b:
        ans = ans + a div b
        a = a mod b
    else:
        ans = ans + b div a
        b = b mod a

527B - Система коррекции ошибок

The first observation is that the new Hamming distance may not be less than the old one minus two, since we change only two characters. So the task is to actually determine, if we can attain decrease by two, one or can’t attain decrease at all.

The decrease by two is possible if there are two positions with the same two letters in two strings but that appear in different order (like “double” <-> “bundle”).

If there are no such positions, then we just need to check that we may decrease the distance. This can be done by just “fixing” the character that stands on the wrong position, like in “permanent” <-> “pergament” (here n stands in wrong pair with m, and there is also unmatched m, so we may fix this position).

Otherwise, the answer is to keep everything as it is. Implementation can be done by keeping for each pair (x, y) of symbols position where such pair appears in S and T and then by carefully checking the conditions above.

528A - Разрезание стекла

Obviously the largest glass piece at any moment is the one that is product of the largest horizontal segment by the largest vertical segment. One of the possible solutions is to carefully implement what described in the statement and keep all horizontal segments and all vertical segments in priority queue or std::set, or some logarithmic data structure. This solution works in .

But there is also a nice linear solution if we answer all queries in reverse order. Suppose segments are not cutting, but merging. In this case we may keep the horizontal and vertical cut lines in double-linked lists and track the current maximum (that can only increase and become equal to the newly-merged segment each time). This solution works in O(k + n + m).

528B - Задача о клике

One may think that this task is about graph theory, but it after some investigation and several equivalent changes in task statement it can be reduced to the well-known greedy problem.

Initially you have that points may lie together in a set if they are not too close, i. e. |x_i - x_j| ≤ w_i + w_j. This is obviously equivalent to the following condition. Let’s consider interval of radius w_i with center in point x_i and call this interval to be the interval of point i. Then the statement actually says that no two such intervals should be intersecting.

This task is well-known and can be solved greedily after sorting segments in ascending order of right endpoint:

Sort segments S in ascending order of S.x + S.w

last = 0
ans = 0
for i = 1..n - 1:
    if S[i].x - S[i].w ⩾ S[last].x + S[last].w:
        last = i
        ans = ans + 1

It’s easy to prove that this solution is correct. Among all ways to choose first k segments, the best way is the one that minimizes x-coordinate of the right endpoint of the last segment (since it restricts us in the least possible way).

528C - Страсти в дата-центре

Problem legend asks you to add minimum number of edges to the given connected undirected graph (possibly, with loops and duplicating edges) and choose direction for its edges so that both the incoming and outgoing degrees of all vertices are even.

First idea is that the resulting graph before we choose the direction (but after we added some edges) will contain Euler circuit, since all degrees are even. That’s almost what we need: if we have an Euler circuit that contains even number of edges, we may direct them like following: a <- b -> c <- d -> e … It’s easy to see that each vertex appearance in this cycle adds 2 to its ingoing or outgoing degree, so the resulting degrees will be even.

But if the Euler circuit is odd (meaning that there is odd number of edges in the graph), we must add some extra edge to the graph before we continue, the easiest way is to add a loop from vertex 0 to itself, since it doesn’t affect the Euler tour, but now tour length is even, so everything is ok.

Now we should think how to add edges optimally. It’s easy to see that the optimal way is to first fix all odd degrees of vertices (i. e. combine all odd vertices by pairs and put an edge in each pair), and then, possibly, add an extra loop as described above. The last part is to actually find an Euler circuit, and to print the answer.

528D - Нечёткий поиск

There were issues with this task. Intended constraints were actually n, m, k ≤ 500000, and the intended solution was using Fast Fourier Transformation, that leads to running time. But unfortunately the statement contained wrong constraints, so we reduced input size during the tour. Nevertheless, we will add the harder version of this task and you will be able to submit it shortly.

Key idea is to reduce this task to a polynomial multiplication. Let’s solve the task in following manner. For each position i of the S for each character c from “ATGC” we will calculate match(c, i) that is equal to the number of c characters that have matching symbol in S if we put string T in position i. Then the criteria for us to have an occurrence at position i is that match(A, i) + match(T, i) + match(G, i) + match(C, i) == |T| (that means exactly that each character from T being put at position i has a corresponding character in S).

Now let’s find out how to calculate match(c, i). Let’s keep only c characters and “not c” characters in both strings and denote them by 1 and 0 respectively. Let’s also spread each 1 in string S by the distance k to the left and to the right. For example, k = 1 for the sample string AGCAATTCAT and the character A corresponding bit vector will be 111110111, and for the character C it will be 0111001110. This bitvector can be calculated in O(n) by putting two events “+1” and “-1” in string S in positions x - k and x + k for each 1 in original string S and then sweeping from left to right over the string S and processing those events.

Now our task is reduced to searching all positions where the bitvector T is the submask of the bitvector S. In constraints n, m, k ≤ 200000 this can be done by using bitsets in O(m(n - m) / 32). Nevertheless, this task can be seen as calculation of polynomials S and reversed(T) product. We will keep this as an exercise for those who decide to submit the harder version of this task.

528E - Треугольники 3000

Let’s draw a bounding box that contains all intersection points. Let’s fix a triangle and consider three angles shown on the picture. Calculate area of intersection of those area with the bounding box and call this area to be the “area of an angle”. Then it’s easy to see, that those three angles are complement to the triangle itself in the bounding box, i. e. triangle area is bounding box area minus three angle areas.

This leads us to the idea how to solve this task by carefully calculating for each possible formed angle on the plane, how much times does it appear in total answer if we sum all values like (S - angle_area(a, b) - angle_area(b, c) - angle_area(c, a)) over all triples (a, b, c) of lines.

Actually, the angle is considered as many times, as many lines there are that intersect both sides of its right adjacent angle. So, our task is reduced to calculate for each angle on plane how much lines intersect its sides (i. e. its rays).

This can be done in by fixing the first side of the angle and then adding lines in ascending order of polar angle, and then by keeping the number of lines that intersect the base line to the left and that intersect the base line to the right. Key idea is that the exact of four angles formed by the pair of lines (a, b) that is crossed by some third line c, can be determined by two numbers: its polar angle alpha and its crossing with a coordinate x. Further details are shown on the picture below.

There is also a nice short O(n²) solution from enot110 here.

Всем привет! Сегодня вечером в обычное время состоится Codeforces Round #296 для обоих дивизионов, автором которого являюсь я.

Готовить задачи мне помогали мои сокомандники, члены команды Moscow SU Trinity sankear и malcolm, а также множество ценных советов дал MikeMirzayanov, за что им всем большое спасибо. Переводом условий мы обязаны нашей бессменной переводчице Delinur.

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

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

UPD: разбалловка — стандартная.

UPD2: в связи с техническими трудностями раунд перенесён на 15 минут вперёд. Приносим извинения за непредвиденную задержку.

UPD3: Приносим свои извинения за проблему с задачей Div1-D. Претест #16 не удовлетворял ограничениям n, m, k <= 200000. Системное тестирование для первого дивизиона будет отложено. Если вы считаете, что этот тест серьёзно повлиял на ваши результаты, вы можете написать мне сообщение, и мы сделаем раунд для вас нерейтинговым.

Системное тестирование во втором дивизионе произойдёт в ближайшее время в обычном порядке.

UPD4: Тестирование завершено. Поздравляем победителей!

Div1:

1. piob

2. PavelKunyavskiy

3. dreamoon_love_AA

4. mnbvmar

5. aid

Div2:

1. happyBirthDayBeni

2. ExfJoe

3. _0029

4. tudort

5. kill-z

UPD5: Был добавлен разбор на английском языке.

Пару дней назад группа мехмата МГУ в контакте репостнула некоторую запись (оригинал — здесь)

Содержание записи следующее:

Мы поздравляем тех, кто успешно сдал сессию и замечательно провёл каникулы и тех, кто закрыл очередной семестр в Техносфере. Надеемся, что все успели отдохнуть, а сейчас предлагаем поразмяться!
В преддверии олимпиады по спортивному программированию Russian Code Cup 2015 лаборатория Технопарка при поддержке MailRu Group объявляет о проведении первого в истории мини-чемпионата BMSTU Code Cup и приглашает всех желающих принять участие!
Квалификационный раунд состоится 22 февраля в 12:00 по Московскому времени. Вас ждёт три задачи, лучшие 20 попадут в финал и будут бороться за первое место. Финал состоится в тот же день через 2 часа после окончания квалификационного раунда и будет состоять из двух задач.
Победитель, занявший первое место, получит денежный приз в размере 15000 руб. Второе и третье места — 10000 и 5000 рублей соответственно.
Регистрируйтесь на участие в чемпионате на http://rcc.tech-mail.ru

На первый взгляд, обычная новость о локальном соревновании МГТУ им. Баумана, если бы вот ссылка не вела на сайт, не отличимый от сайта Russian Code Cup. Насколько я могу судить, по этому адресу располагается какая-то дикая мешанина из информации, относившейся к RCC, и информации, относящейся к этому соревнованию (например, время квалификации и финала на BMSTU Code Cup). Например, по ссылке "правила" открываются правила RCC.

Более того, насколько я могу видеть, никакой информации об этом соревновании в сети нет кроме двух следующих постов ВК (доступны в том числе незалогиненным в соцсеть): пост1, пост2.

К первой записи в комментариях резонно указывают, что время не самое удачное — в этот же день в то же время проходит OpenCup, гран-при Удмуртии. На что, видимо, кто-то из организаторов (надо сказать, слегка невпопад) отвечает, что в это же время могут быть и региональные олимпиады по программированию, и это дело каждого — выбирать, в чём участвовать.

Возникают вопросы. Действительно ли это доступное для всех мероприятие, в котором может участвовать любой желающий? Если да, то работа по доведению информации о соревновании до аудитории проделана на твёрдую двойку: в сети ни одного упоминания об BMSTU Code Cup, нормальных правил — не найти (только относящиеся к RCC, что явно не актуально), время действительно выбрано не самое удачное.

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

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

Кто-нибудь знает что-нибудь об этом соревновании?

Обратите внимание на изменения в расписании для новогоднего контеста Good Bye 2014. Раунд начнётся в 30 декабря в 18:00 MSK, будет длиться два с половиной часа и будет общим для двух дивизонов.

Ждите детали в анонсе. С наступающим новым годом!

Всем доброго времени суток!

Сегодня в 12:00 по Москве состоится Codeforces Round #279, предназначенный для участников второго дивизиона. Раунд проходит на задачах муниципиального (II) этапа всероссийской олимпиады школьников по информатике 2014-2015 учебного года, который проходит в это же время в Саратове.

Раунд подготовила для вас дружная команда Saratov SU 2, членами которой в разное время являлись и являются ikar, HolkinPV, IlyaLos, fcspartakm.

Вам будет предложено 6 задач на 2 часа 30 минут. Разбаловка будет оглашена непосредственно перед раундом.

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

UPD: Разбалловка — 500-1000-1500-2000-2000-2500.

Удачи!

Я сегодня получил такое письмо:

Уважаемые финалисты!

Спешим уведомить вас о нескольких изменения по проведению финала RCC 2014:

• финал будет проведен в субботу 4 октября с 11:00 до 14:00

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

• как призовой фонд, так и количество призеров увеличены. Призовой фонд увеличен до $25000, и по новым правилам призы получит не лучшая тройка, а лучшая десятка участников: за 1 место приз составит $10000, за 2 место — $5000, за 3 место — $3000, участники, занявшие 4, 5, 6, 7, 8, 9 и 10 места, получат по $1000.
• по месту проведения награждения призеров уведомим отдельно — выбираем между двумя вариантами

Спасибо!

Команда Russian Code Cup.

Нет слов, чтобы описать моё разочарование. Ты, наконец-то, проходишь на онсайт престижного российского соревнования, и тут выясняется, что онсайта-то как такового и не предвидится =(

Code Jam R3 starts today at 14:00 UTC. Don't miss!

Top-25 contestants will pass to onsite this August in Google's LA office.

Code Jam R2 starts today at 14:00 UTC. Don't miss!

Top 1000 contestants will receive t-shirts.

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

Не дело =(

Завтра в 19:00 по Москве состоится SRM #613. Не пропустите!