Блог пользователя Serega

Автор Serega, 11 лет назад, По-русски

Всем привет!

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

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

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

Автор Serega, 11 лет назад, По-русски

332A - Выпьем?

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

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

Код

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

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

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

Код

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

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

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

Код

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

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

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

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

Код

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

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

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

Рассмотрим две произвольные различные вершины s, t. Пусть v1, v2, ..., vl — все различные общие смежные вершины этих двух вершин. Если l ≥ k, то мы получим, что вершины из множества {v1, ..., vk} имеют две общие смежные вершины s, t, что противоречит (*). Пусть теперь l ≤ k - 2. Рассмотрим множество вершин S = {s, t, v1, ..., vl}, состоящее из 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 = {v1, ..., vk, vk + 1}, в котором v1, ... vk — произвольные попарно различные вершины нашего графа, vk + 1 — их общая смежная вершина. Приведем конструктивный способ построения полного подграфа на основе этого множества. Осуществим k - 1 итерацию, на i-ой итерации будем рассматривать вершину vi. Если эта вершина смежна со всеми вершинами vi + 1, ..., vk, то перейдем к следующей итерации. Иначе рассмотрим множество T = {v1, ..., vi - 1, vi + 1, ...vk + 1}. У вершин из T существует ровно одна общая смежная вершина u (не совпадающая, очевидно, с vi, поскольку vi смежна не со всеми вершинами из T). Заменим вершину vi на u и перейдем к следующей итерации. После окончания последней итерации множество S, очевидно, будет являться множеством вершин полного подграфа.

Покажем, что при k ≥ 3 наш граф — это полный граф из k + 1 вершины. Согласно лемме 2, в этом в графе найдется полный подграф с множеством вершин S = {v1, ..., vk + 1}. Допустим, что в нашем графе найдется вершина u, не принадлежащая S. Так как S — множество вершин полного подграфа, а любые две вершины согласно (1) имеют ровно k - 1 общую вершину, то все общие смежные вершины v1 и v2 (как и любых двух различных вершин из S) лежат в S. Если любые k вершин имеют общую смежную вершину, то и любые i (2 ≤ i ≤ k - 1) вершин имеют общую смежную вершину (возможно, не единственную). В частности, поскольку k ≥ 3, общую смежную вершину имеют вершины v1, v2, u, и эта вершина принадлежит S (как общая смежная вершина v1 и v2). Если допустить, что у 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 в этом блоке. Решим задачу динамическим программированием: di, j – верно ли, что существует ключ, первые i символов которого – нули и при использовании которого будет выписана строка, получаемая конкатенацией всех (q, j)-суффиксов сообщения. Переходы в этой динамике основаны на постановке в i-ую позицию ключа либо нуля, либо единицы (каждый раз нужно выбирать минимальный допустимый символ). Для восстановления самого ключа требуется сохранять для каждой подзадачи и сами выбранные символы, либо анализировать сами значения динамики.

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

Код

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

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

Автор Serega, 11 лет назад, По-русски

Всем привет!

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

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

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

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

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

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

Williamacm

Windseeker

Tifuera

seen

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

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

Автор Serega, 13 лет назад, По-русски

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

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

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

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

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

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

3 2
1 2 3
2
1
2

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

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

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

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

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

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

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

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

Задача 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]) для строки s1 = r(a) + '\0' + b и z-функцию (z[i]) для строки s2 = 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
  • Проголосовать: нравится
  • +24
  • Проголосовать: не нравится

Автор Serega, 13 лет назад, По-русски

Всем привет!

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

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

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

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