Если gcd(n, f(n))! = 1, то -1. Иначе,находим минимальное число m, такое что a^m + 1 = a(mod n). Тогда n^k - 1 должно делиться на m. И находим минимальное такое k. Это и будет ответ. UPD В 46 тесте кажется что-то вроде N=51,ответ должен быть 4.

A: просто переберём границу. Для границы между 0 и 1 суммой ошибок будет количество W во входных данных. Теперь научимся переходить от границы между i и i + 1 к границе между i + 1 и i + 2. Поймём, что это означает переход префектуры i + 1 из восточной части в западную, поэтому из ошибок надо вычесть количество W и добавить количество E в столбце i + 1 входных данных (в 1-индексации). Для всех вариантов границы найдём тот, который даёт минимум ошибок

Изначально имеем площадь 2 * (a * b + a * c + b * c). Каждый раз когда удаляем кубик считаем сколько сторон его входят в ответ(x) и сколько не входят(y). Ответ меняется на  + y - x. code

Скорее стрелочке. У нас по тексту был WA15, а по стрелочке — TL26.

я верил стрелочке -- OK

Вариация на тему convex hull trick #2. Уже 2ой opencup подряд задача на трюк из этого списка.

(Upd. забыл важную деталь — решение надо писать на C++, на Java оно не лезет в ТЛ; на плюсах впрочем лезет менее чем с 2x запасом, что наводит на мысль, что у жюри есть что-то в константу раз быстрее)

Можно подробнее про решение? Как учесть пересечения отрезков? Иногда нужно делить отрезки на два в точке их пересечения, чтобы улучшить ответ. Если же мы будем учитывать все пересечения, то количество отрезков может увеличиться до n² и min cost паросочетание не зайдет по времени.

А эту задачу можно решить если нет условия связности, то есть в условии не было бы дано что граф изначально связан (если убрать направления ребер)?

Заходит попроще.

Будем рассматривать вершины в порядке увеличения продуктивности, и поддерживать для каждой вершины параметр "у ее новых соседей продуктивность должна быть не ниже Х". Если у всех вершин разные продуктивности, то уже вроде должна работать обычная жадность — берем очередную вершину, ставим ей максимум из ограничений по ее соседям, пересчитываем ограничения по ее соседям.

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

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

А как быстро определять компоненты в группах равных?

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

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

Получили DAG. В этом DAG для каждой вершины посчитаем максимальное расстояние, на которое можно из нее уйти (для листа считаем, что оно равно 1) — это простая динамика. Легко заметить, что вот эта величина как раз и равна зарплате всей компоненты, которую представляет эта вершина DAG

А как жадно считать ответ? Брать вершины в порядке возрастания производительности?

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

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

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

Как обычно :)

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

Сделаем сканлайн и в декартовом дереве будем хранить ребра. При этом, если ребро идет слева направо с коэффициентом +1, а если справа налево, то -1. Чтобы определить, находится ли точка хотя бы в одном многоугольнике, спустимся по дереву и найдем префикс сумму. Если она отлична от нуля, то значит точка лежит внутри многоугольника.

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

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

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

1. Существует два запроса, для которых мы хотим доставить еду по кратчайшему пути, эти два пути пересекаются и направлены в разные стороны.

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

Чтобы найти противоречие первого типа, будем идти по порядку запросов и в каком-нибудь дереве отрезков проставлять +1/-1 (в зависимости от направления) пока не получится так, что в какую-то клетку (которая соответствует некоторому ребру) захотим поставить два разных числа.

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

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

Это решение, наверное, не самое простое, но кода довольно мало:

Есть два варианта: 1) либо всё ориентируем по циклу в одну из двух сторон. 2) есть вершина, из которой оба ребра выходят.

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

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

Всего будет O(N) перекидываний, так что нужно лишь иметь структуру, которая умеет говорить, есть ли при заданном способе выполнения заданий противоречие. Например, подойдёт дерево интервалов, которое для каждого отрезка помнит "есть ли там рёбра налево" (ну точнее чтобы поддерживать "есть ли", видимо нужно помнить сколько), "есть ли там рёбра направо", "есть ли там противоречия".

Списками. Без шаблона кода строк сто, но он размашистый и очень простой.

Вот моё решение со списками — немного копипасты, но в целом простое: http://pastebin.com/idsQa8WZ

Для каждой вершины хранить соседние на 4 стороны (сортировка за N log N). Для каждой начальной точки копируем всю структуру, чтобы можно было удалять вершины когда мы прошли по ним. В итоге N*N

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

у нас было решение с DSU, которое хранило следующую не удаленную из текущей вершины.

Динамика.

Сначала для каждой вершины посчитаем лучшую дорогу от нее для выступления, т.е. с максимальным v/d(т.е. максимальный результат за секунду), пусть это будет массив best_road[i]

После этого напишем динамику dp[time][v] — максимальный результат, который можно достичь за time секунд от начала на v вершине.

Основа динамики dp[0][1] = 1, для каждого ребра(x,y) переходы dp[i+d][y] = max(dp[i+d][y],dp[i][x] + v), dp[i+d][x] = max(dp[i+d][x],dp[i][y] + v)

Ответом будет максимум dp[time][v]*2 + (P-time*2)*best_road[v] по time = 0..P/2, v = 1..n

Есть только одна вершина, в которой мы будем стоять на месте, переберем ее, когда мы знаем где стоим с эффективностью v/d, мы можем найти путь по ребрам Исходная цена-V/d, чтобы этот путь был мнимален по такой цене. При этом идти только по ребрам с положительной ценой(иначе будет находить пути с большим временем, но положительной эффективностью), получаетс N *N^2.

I: Firstly, if we will use songs with numbered song_i1, song_i2, ..., song_ik, then the total satisfaction will be maximized, if f_i1 ≤ f_i2 ≤ ... ≤ f_ik or f_i1 ≥ f_i2 ≥ ... ≥ f_ik. We wil sort of f_i. Let's dp(i,j) — first i songs assigned and j total length of songs.

dp(i, j) = max{dp(k, j - t_i) + p_i - (f_i - f_k)²} = max{dp(k, j - t_i) - f_k² + 2f_kf_i} + p_i - f_i² Then we can use convex hull trick optimization. Code

Hi, I'm the writer of the problem C and H. How was the problems?

I posted the solution of the problem D here.

I'm the writer of the problem J. I posted my brief editorial for this problem as a blog entry.

Кнопочка в правом верхнем углу, справа от "объявлений жюри"