Всем привет!

14 ноября, 19:30 MSK состоится Codeforces Round #212 (Div. 2), который был подготовлен коллективом авторов из Саратовского государственного университета в составе: Артем Седанов (FunkyCat), Сергей Сухов (Serega), Ольга Чикатуева (Helga), Дмитрий Зайцев (My-my).

Выражаем благодарность координатору раундов Геральду Агапову (Gerald) за полезные советы и Марии Беловой (Delinur) за перевод условий на английский язык.

Всем удачи и высокого рейтинга!

UPD1. В раунде будет использована динамическая система оценки сложности задач (см. здесь).

UPD2. Разбор задач опубликован здесь.

UPD3. Рейтинг обновлен. Поздравляем победителей, решивших по 4 задачи:

1. CleRIC

2. i_must_learn_matan

3. Dshavn

4. gzh1998n

332A - Выпьем?

Поскольку n ≥ 4, один ход Васи никак не влияет на то, выпьет ли он стакан сока во время другого своего хода. Следовательно, задача заключается просто в том, чтобы найти в заданной строке количество позиций, номера которых (в 0-индексации) кратны n и перед которыми стоит хотя бы три одинаковых символа.

Асимптотика решения — O(|s|)

Код

332B - Максимальная абсурдность

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

Асимптотика решения — O(n).

Код

332C - Месть студентов

Отсортируем приказы в первую очередь по возрастанию b_i, а при равенстве b_i — по убыванию a_i. Можно считать, что в оптимальном решении все приказы, выполненные заведующей, следуют (в отсортированном списке) после тех приказов, которые она не выполнила (это может быть неверно в случае наличия одинаковых приказов, однако на параметры ответа это все равно не влияет). Переберем i — номер первого приказа в отсортированном списке, который выполнит заведующая. Слева от этого приказа нужно выбрать p - k приказов, которые заведующая не выполнит. Поскольку требуется, что сумма b_i у этих приказов была наибольшей, можно выбрать последние p - k приказов, стоящие перед i-ым приказом. Справа от i-ого приказа требуется выбрать k - 1 приказ, который заведующая выполнит. Требуется, чтобы эти приказы имели максимальную сумму a_i. Если i перебирать по убыванию, то эту максимальную сумму можно поддерживать, просто храня k - 1 максимальных a_i из уже проанализированных в какой-нибудь стандартной структуре данных, работающей за логарифмическое время (типа multiset’а в C++),

Асимптотика решения — O(n log n).

Код

332D - Похищение чертежей

В задаче задан неориентированный взвешенный граф без кратных ребер и петель, удовлетворяющий следующему свойству: для любого k-элементного множества S его вершин существует единственная вершина, смежная со всеми вершинами этого множества (*) (эта вершина была названа в условии соседней с S). Для любого k-элементного множества можно вычислить специальную характеристику, равную сумме весов ребер, ведущих из вершин этого множества в соседнюю с ним вершину. Требуется найти среднее арифметическое характеристик всех k-элементных множеств вершин.

Решить эту задачу позволяет следующий факт (доказательство которого приведено ниже): при k ≥ 3 условию задачи удовлетворяет только полный граф из k + 1 вершины. Для полных графов ответ на задачу равен удвоенной сумме длин всех ребер, деленной на n. Точно так же вычисляется и ответ для k = 1. Осталось рассмотреть случай k = 2. Переберем вершину i, которая будет являться соседней с нашим двухэлементным множеством. Выпишем в порядке возрастания все такие номера вершин j, что c_i, j ≠  - 1. Любые две вершины из построенного списка образуют множество, для которого вершина i является соседней, а других таких множеств не существует. Перебирая все пары вершин из этого списка, мы можем прибавить характеристики всех этих множеств к ответу. Поскольку в задаче гарантируется, что граф удовлетворяет свойству (*), то каждая пара вершин будет проанализирована ровно один раз. Отметим, что аналогичный подход используется и в валидаторе к данной задаче.

Асимптотическая сложность решения составляет, таким образом, O(n²)

Код

Доказательство.

Пусть в графе любые k вершин имеют ровно одну общую смежную вершину (*)

Лемма 1. У любых двух вершин ровно k - 1 общая смежная вершина.

Рассмотрим две произвольные различные вершины s, t. Пусть v₁, v₂, ..., v_l — все различные общие смежные вершины этих двух вершин. Если l ≥ k, то мы получим, что вершины из множества {v₁, ..., v_k} имеют две общие смежные вершины s, t, что противоречит (*). Пусть теперь l ≤ k - 2. Рассмотрим множество вершин S = {s, t, v₁, ..., v_l}, состоящее из l + 2 ≤ k элементов. Если l + 2 < k, дополним это множество до k-элементного произвольными вершинами, не входящими в S. Полученное множество назовем T. Согласно (*), существует единственная вершина u, не входящая в T, которая смежна со всеми вершинами из T. В частности, эта вершина смежна с вершинами s и t. Однако по построению во множестве T должны были находиться все вершины, смежные c s и t, в том числе и вершина u. Получили противоречие. Значит, l = k - 1.

Лемма 2. В нашем графе найдется полный подграф из k + 1 вершины.

Рассмотрим множество S = {v₁, ..., v_k, v_k + 1}, в котором v₁, ... v_k — произвольные попарно различные вершины нашего графа, v_k + 1 — их общая смежная вершина. Приведем конструктивный способ построения полного подграфа на основе этого множества. Осуществим k - 1 итерацию, на i-ой итерации будем рассматривать вершину v_i. Если эта вершина смежна со всеми вершинами v_i + 1, ..., v_k, то перейдем к следующей итерации. Иначе рассмотрим множество T = {v₁, ..., v_i - 1, v_i + 1, ...v_k + 1}. У вершин из T существует ровно одна общая смежная вершина u (не совпадающая, очевидно, с v_i, поскольку v_i смежна не со всеми вершинами из T). Заменим вершину v_i на u и перейдем к следующей итерации. После окончания последней итерации множество S, очевидно, будет являться множеством вершин полного подграфа.

Покажем, что при k ≥ 3 наш граф — это полный граф из k + 1 вершины. Согласно лемме 2, в этом в графе найдется полный подграф с множеством вершин S = {v₁, ..., v_k + 1}. Допустим, что в нашем графе найдется вершина u, не принадлежащая S. Так как S — множество вершин полного подграфа, а любые две вершины согласно (1) имеют ровно k - 1 общую вершину, то все общие смежные вершины v₁ и v₂ (как и любых двух различных вершин из S) лежат в S. Если любые k вершин имеют общую смежную вершину, то и любые i (2 ≤ i ≤ k - 1) вершин имеют общую смежную вершину (возможно, не единственную). В частности, поскольку k ≥ 3, общую смежную вершину имеют вершины v₁, v₂, u, и эта вершина принадлежит S (как общая смежная вершина v₁ и v₂). Если допустить, что у u есть две смежных вершины x, y из S, то получим противоречие (1) (поскольку у этих двух смежных вершин будет k общих смежных вершин). Следовательно, в S существует единственная вершина x, смежная с u. Возьмем вершину y из S, отличную от x. У вершин (u, x, y) есть общая смежная вершина, и она принадлежит S. Но это значит, что u имеет две смежных вершины из S. Противоречие.

332E - Двоичный ключ

Переберем cnt — количество единичных бит в ключе. Заметим, что cnt достаточно перебирать до min(|s|, k), поскольку ключи, содержащие более чем |s| единичных бит, не могут являться минимальными лексикографически.

Научимся решать задачу для фиксированного cnt. Заметим, что любой полный проход по ключу соответствует выписыванию cnt из k просмотренных символов контейнера, т.е. контейнер разбивается на блоки длины k, а сообщение — на блоки длины cnt (последние блоки могут иметь меньшую длину). Пронумеруем символы каждого блока сообщения от 0 до cnt–1. Назовем (q, j)-суффиксом сообщения суффикс его q-ого блока, начинающийся с позиции j в этом блоке. Решим задачу динамическим программированием: d_i, j – верно ли, что существует ключ, первые i символов которого – нули и при использовании которого будет выписана строка, получаемая конкатенацией всех (q, j)-суффиксов сообщения. Переходы в этой динамике основаны на постановке в i-ую позицию ключа либо нуля, либо единицы (каждый раз нужно выбирать минимальный допустимый символ). Для восстановления самого ключа требуется сохранять для каждой подзадачи и сами выбранные символы, либо анализировать сами значения динамики.

Асимптотическая сложность решения — O(k·|s|² + |p|).

Код

Всем привет!

Через несколько дней (24 июля, 19:30 MSK) состоится Codeforces Round #193 (Div. 2), который был подготовлен мной. Те, кто уже вышел в первый дивизион, традиционно могут поучаствовать в раунде вне конкурса.

Хотелось бы поблагодарить Виталия Гриднева (gridnevvvit), Павла Кунявского (PavelKunyavskiy) и Дмитрия Иванова (DmitriyIvanov) за тестирование задач, координатора раундов Геральда Агапова (Gerald) за полезные советы и Марию Белову (Delinur) за перевод условий на английский язык.

Всем удачи и высокого рейтинга!

UPD1. В раунде будет использоваться динамическая разбалловка (см. здесь). Задачи будут расположены в порядке возрастания предполагаемой сложности.

UPD2. Опубликован разбор задач.

UPD3. Рейтинг участников обновлен. Поздравляем победителей, решивших 4 задачи:

Williamacm

Windseeker

Tifuera

seen

Задача A. Эпическая игра (автор - dudkamaster).

Авторское решение: http://pastebin.com/zRiQwy6u

В этой задаче достаточно было просто промоделировать описанную игру. Искать наибольший общий делитель можно любым разумным способом.

Задача B. Перед экзаменом (автор - Serega).

Авторское решение: http://pastebin.com/kBjCwiiD

Рассмотрим решение задачи для максимального уровня знаний; для минимума задача решается аналогично. Понятно, что максимальный уровень может достигаться либо на билете, который уже попался кому-то из студентов, либо на билете, точное содержание которого нам ещё не известно. Для анализа первого случая можно попутно с чтением входных данных подсчитывать уровни знаний по билетам и выбирать максимальный из них. Второй случай хитрее. Отсортируем все теоремы, не вошедшие в другие билеты, по невозрастанию уровню знаний. Понятно, что искомый билет будет состоять из первых теорем в этом списке. Однако здесь возникает один очень важный случай, которого и не учитывало авторское решение: для того чтобы такая ситуация была реализуема, необходимо, чтобы количество различных известных нам билетов было строго меньше общего числа билетов. Эту ситуацию демонстрирует, например, тест

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

Асимптотическая сложность решения - O(n(q + log(n)).

Задача C. Реформа образования (автор - Serega).

Авторское решение: http://pastebin.com/eZhJYGpC

Данная задача решается при помощи динамического программирования. Отсортируем все предметы в порядке неубывания сложности. Пусть d[i][j][z] - наибольшее суммарное число упражнений, которое можно задать, если расписание содержит ровно z предметов из числа первых i (в отсортированном порядке), включает в себя i-ый предмет, а количество упражнений по i-ому предмету равно a_i + j.

Рекуррентные соотношения основаны на переборе предмета, который будет стоять в расписании в z - 1 день. Для восстановления ответа необходимо сохранить исходные номера предметов, а при вычислении динамики - сохранять предков.

Асимптотическая сложность решения - O(m²· n· max(b_i - a_i)).

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

Задача D. Преобразование строки (автор - Serega).

Авторское решение: http://pastebin.com/puGK1WYh

Если длины входных строк не равны, сразу выведем "-1 -1" и завершим программу. Иначе положим число n равным длине входных строк.

Будем перебирать число i. Научимся за O(1) понимать, для какого наименьшего j подстроку b[0... n - i - 1] можно представить в виде a[i + 1... j - 1] + r(a[j... n - 1]). Для этого посчитаем префикс-функцию (p[i]) для строки s₁ = r(a) + '\0' + b и z-функцию (z[i]) для строки s₂ = b + '\0' + a. Понятно, что для фиксированного i искомым значением j станет n - p[2n - i - 1], при этом подстроки a[i + 1... j - 1] и b[0..j - i] должны совпадать (1). Последнее утверждение несложно проверить, используя подсчитанную z-функцию. Также тривиально доказательство того факта, что если при фиксированном i свойство (1) не выполняется для выбранного нами j, то оно не выполнится и для больших j.

Асимптотическая сложность решения - O(n).

Задача E. Другая реальность (автор - Kenny_HORROR).

Разбор размещён здесь.

Всем привет!

Добро пожаловать на Codeforces Beta Round #90! Сегодняшний контест для вас подготовили студенты Саратовского государственного университета - я, Сергей Сухов, и Александр Игнатьев (aiMR). Благодарим Артема Рахова (RAD) за помощь и ценные советы, Марию Белову (Delinur) за перевод условий и Михаила Мирзаянова (MikeMirzayanov) за возможность провести этот раунд.

Удачи и высокого рейтинга!