Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

Разбор Codeforces #484 Round (Div. 2)

Revision ru11, by AGrigorii, 2018-05-18 22:34:38

982A - Row

Из двух, описанных в условии правил, следует, что рассадка является <<максимальной>> тогда, когда в ней не встречаются две единички рядом или три нолика. Также необходимо аккуратно обработать концы данного ряда — надо проверить, что нельзя посадить человека на самый правый или самый левый стул.

982B - Bus of Characters

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

  1. Сортируем массив длин рядов по возрастанию
  2. Для каждого интроверта пишем номер очередного свободна ряда и добавляем его в стек
  3. Для каждого экстраверта пишем последнее число из стека и удаляем его оттуда

982C - Cut 'em all!

Заметим, что если есть какое-то ребро, которое можно удалить, то мы можем сделать это, без каких-либо последствий. Рассмотрим такое ребро, что в одном из полученных поддеревьев уже точно нельзя удалить больше, а его удаление возможно. Что произойдет, если мы его оставим в дереве? Относительно другого конца ребра четность поддерева не изменилась, что означает, что на дальнейшие удаления это ребро не повлияло. А значит, если мы его удалим, то ответ улучшится. Отсюда следует жадное решение: в дфс-е насчитываем для каждой вершины размер поддерева, включая текущую вершину, и если он четен, то ребро в потомка (если он существует), можно удалить.

982D - Shark

Давайте посортируем массив и будем вставлять числа в порядке сортировки от меньшего к большему. Используя структуру данных "Система непересекающихся множеств" можно легко поддерживать информацию о текущем количестве отрезков, а также используя map внутри функции объединения, и информацию о текущих размерах отрезков (локаций). Тогда остается лишь обновлять ответ, когда это требуется.

982E - Billiard

Если симметрично отражать прямоугольник на плоскости относительно своих сторон, то новая траектория движения шара окажется куда проще. А именно — прямой. Одно из возможных решений такое:

  1. Если вектор направлен под углом в 90 градусов к осям, то пишем if-ы.
  2. Иначе поворачиваем поле таким образом, чтобы вектор удара стал (1, 1).
  3. Выписываем уравнение прямой движения шара:  – 1·x + 1·y + С = 0. Если подставим изначальное положение шара, то найдем коэффициент C.
  4. Заметим, что в бессконечно замощенной плоскости координаты любой лузы представимы в виде (k1·n, k2·m).
  5. Подставим координаты лузы в уравнение прямой шара. Получается диофантово уравнение A·k1 + B·k2 = C. Оно разрешимо в случае, если C | gcd(A, B). В противном случае решений нет.
  6. Из всех решений данного диофантово уравнения нас интересует наименьшее на положительной полуоси.
  7. По найденным k1, k2 легко получить координаты соответствующей им лузе
  8. Повернуть поле обратно, если требуется.

982F - The Meeting Place Cannot Be Changed

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

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

Рассмотрим только циклы, которые выходят из вершины главного цикла, приходят в какую-то вершину главного цикла, а дальше движутся по главному циклу и замыкаются. Если цикл выходит из главного цикла, то он должен на него вернуться где-то дальше по направлению главного цикла, при этом не перескакивая отмеченные вершины с ответом (иначе будет пустое пересечение, а мы предположили, что не пустое) (считаем, что если цикл вернулся не по главному циклу туда же, откуда вышел, то он совершил скачок длинной весь главный цикл, а не 0). От вершины, в которой рассматриваемый цикл возвращается на главный, до вершины, из которой он выходит с главного, проведём дугу в направлении главного цикла. Те вершины главного цикла, которые такая дуга не покрывает, заведомо не могут являться ответом. Пересечение всех рассмотренных циклов с главным определяется пересечением всех таких дуг.

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

Теперь нужно отметить все дуги между возвратом-выходом с главного цикла. Для этого будем запускать dfs из всех вершин главного цикла и пытаться вернуться на главный цикл как можно дальше (расстояние измеряется по количеству вершин главного цикла между выходом и возвратом). Как было отмечено выше, циклы, выходя и возвращаясь, не могут перескакивать ответ. Значит все dfs'ы, стартующие между границами ответов, стремятся к какой-то вершине главного цикла, которая является граничной в дуге с возможными ответами. Значит если в одном dfs'е мы выбрали самую удалённую вершину из нескольких вариантов, то в другом dfs'е рассматриваемые варианты не поменяются ролями, и старая самая удалённая вершина так и останется самой удалённой среди тех же вариантов в новом dfs'е. Значит можно запускать все dfs'ы с общим массивом used, в котором кэшировать самую удалённую вершину.

В итоге решение сводится к тому, чтобы найти главный цикл, отсортировать его вершины по направлению обхода, запустить из них из всех dfs’ы с общим массивом used’ов, между стартом и финишом всех dfs’ов отметить дуги и пересечь их все, на пересечении всех дуг взять ответ. Если после удаления вершины-ответа в графе не останется больше циклов, то это действительно ответ, а иначе предположение было не верно и ответа не существует.

Tags round, 484, div2, edirorial

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English AGrigorii 2018-05-20 14:25:09 1558
en1 English AGrigorii 2018-05-20 14:20:09 5855 Initial revision for English translation
ru14 Russian AGrigorii 2018-05-18 22:38:03 0 (опубликовано)
ru13 Russian AGrigorii 2018-05-18 22:36:23 4 Мелкая правка: ' является <<максимальной>> тогда, ко' -> ' является максимальной тогда, ко'
ru12 Russian AGrigorii 2018-05-18 22:35:24 4
ru11 Russian AGrigorii 2018-05-18 22:34:38 1
ru10 Russian AGrigorii 2018-05-18 22:33:53 9
ru9 Russian AGrigorii 2018-05-18 22:33:26 2954
ru8 Russian AGrigorii 2018-05-18 22:31:49 20
ru7 Russian AGrigorii 2018-05-18 22:31:29 140
ru6 Russian AGrigorii 2018-05-18 22:29:24 8
ru5 Russian AGrigorii 2018-05-18 22:27:42 315
ru4 Russian AGrigorii 2018-05-18 22:21:46 645
ru3 Russian AGrigorii 2018-05-18 22:12:31 423
ru2 Russian AGrigorii 2018-05-18 22:08:00 932
ru1 Russian AGrigorii 2018-05-18 21:43:27 967 Первая редакция (сохранено в черновиках)