# Разбор Div. A > Дорешка по разбору - самое важное в СП. Если вы не дорешиваете, вы ничему не учитесь. :::warning Совет: не лезьте в разбор сразу же. В идеале, подумайте над задачей где-то 20-30 минут, и только потом читайте разбор. ::: # [ZZ1. Не добавлять](https://codeforces.com/group/thOWHpwJb2/contest/479788/problem/ZZ1) :::spoiler Подсказка 1 :::info Вы можете симулировать процесс ::: :::spoiler Подсказка 2 :::info Воспользуйтесь гармоническим рядом ::: :::spoiler Разбор :::info Давайте перебирать текущее число $x$ от $1$ до $10^6$. Убедимся, что нашего числа ещё не было в начальном массиве. Теперь для него будем перебирать дополнительный множитель $y$ на который будем домножать наше число. Посчитаем НОД по всем $x*y$, которые встречаются в массиве. Если итоговый НОД будет равен $x$, то увеличим ответ на 1. Это работает быстро из-за следующего факта: $N+\frac{N}{2} + \frac{N}{3} + \frac{N}{4} + ... + \frac{N}{N}$ приблизительно равно $NlogN$ ::: # [ZZ2. Плохая генетика](https://codeforces.com/group/thOWHpwJb2/contest/479788/problem/ZZ2) :::spoiler Подсказка 1 :::info Сколько всего существует способов выбрать 3 человека из $n$? ::: :::spoiler Подсказка 2 :::info Посчитайте количество плохих троек и отнимите от общего числа троек ::: :::spoiler Подсказка 3 :::info Плохую тройку определяют только минимальное и максимальное число ::: :::spoiler Подсказка 4 :::info Отсортируйте массив и перебирайте максимальное число из тройки ::: :::spoiler Разбор :::info Зафиксируем текущий максимум $a_i$ у него есть какие-то делители. Посмотрим на все числа которые мы встретили до $i-ого$, которые делятся на текущий делитель $d_i$. Пусть у данного числа позиция в отсортированном массиве равна $j$, тогда мы можем зафиксировать данное число в качестве минимума. Тогда все числа из отрезка $[j ; i]$ подходят в качестве треьего числа. Сразу же можно заметить, что можно перебирать не все делители числа, а только те у которых в факторизации у каждого простого числа степень 0 или 1. Таких делителей в худшем случае $2^7$. Но у нас возникнут пересечения(так как одно и тоже число может делиться сразу на несколько делителей максимума). Поэтому воспользуемся принципом включений-исключений. Если текущий делитель содержит нечётное колчиество простых делителей, то мы должны прибавить $j-i$, иначе отнять. Если объединить все наши наблюдения получаем решение. Поддреживаем все уникальные делители на префиксе. На каждом шаге проходимся по позициям, которые кратны текущему делителю и пересчитываем ответ при помощи преф. сумм. Итоговая асиптотика: $n * 2^7 * 7$ (https://codeforces.com/blog/entry/111841) - оригинальный разбор ::: # [ZZ3. XOR-инверсии](https://codeforces.com/group/thOWHpwJb2/contest/479788/problem/ZZ3) :::spoiler Подсказка 1 :::info Решайте задачу побитово ::: :::spoiler Подсказка 2 :::info А может быть битовый бор? ::: :::spoiler Подсказка 3 :::info Храните в вершине бора сколько чисел через неё проходит ::: :::spoiler Разбор :::info Для решения задачи давайте посчитаем массив $kol[32][2]$, $kol_{i,j}$ будет для каждого бита говорить сколько инверсий добавится за счёт данного бита, если $i-ый$ бит искомого числа будет равен $j$. Для восстановления ответа пройдёмся по всем битам и просто выберем минимум из $kol_{i,0}$ и $kol_{i,1}$. Научимся считать данный массив. Давайте идти по заданному массиву и добавлять число в битовый бор. При добавлении в бор будем идти от старшего бита(32-ого) к младшему. Пусть у нас есть какое-то множество чисел, которые пришли в текущую вершину. Заметим, что у них одинаковый префикс старших битов, а это значит, что после операции XOR старшие биты у них останутся одинаковыми. Пусть у нас сейчас добавляется число с единичным битом. Посмотрим сколько у нас чисел в этом бите с единичным битом и сколько с нулевым.Если мы проксорим с единицей данный бит, то у текущего числа бит станет нулём, а к числу инверсий прибавится кол-во чисел с нулевым битом. Иначе при ксоре с нулём никаких инверсий данное число добавлять не будет. Если у добавляемого числа сейчас нулевой бит, то если мы не будем ксорить его, то все числа с едничным битом будут давать нам инверсию. А при ксоре с едницей текущее число инверсий добавлять не будет. ::: # [andrewns1. Инженер Артём](https://codeforces.com/group/thOWHpwJb2/contest/479788/problem/andrewns1) :::spoiler Подсказка 1 :::info Решите задачу для матрицы из нулей. ::: :::spoiler Подсказка 2 :::info Прибавляя $1$ к элементу, вы меняете его чётность. ::: :::spoiler Подсказка 3 :::info Если у двух элементов не совпадает чётность, то они точно не совпадают. ::: :::spoiler Разбор :::info Операция прибавления $1$ позволяет изменить чётность любого числа в матрице. Раскрасим матрицу в шахматном порядке и прибавим к некоторым элементам $1$, чтобы получить нужную чётность. Тогда любые два соседних по стороне элемента имеют разную чётность и следовательно не равны. Асимптотика: $O(nm)$. ::: # [andrewns2. Сложные вычисления](https://codeforces.com/group/thOWHpwJb2/contest/479788/problem/andrewns2) :::spoiler Подсказка 1 :::info Переберите ответ. Пусть сейчас мы перебираем $x$, тогда он является ответом, если не существует отрезка с MEX равным $x$. ::: :::spoiler Подсказка 2 :::info Рассмотрим все вхождения числа $x$. Пусть их индексы --- $i_1, i_2, ..., i_k$. Тогда если существует отрезок с MEX равным $x$, то существует отрезок $[i_j; i_{j+1}]$ с MEX равным $x$. Как быстро находить MEX на этих отрезках? ::: :::spoiler Разбор :::info Давайте будет перебирать ответ. Пусть текущий ответ это $x$, тогда мы можем получить его только тогда, когда не существует подмассивов, у которой MEX равен $x$. Заметим, что нам нужно проверить MEX подмассивов, которые находятся между всеми вхождениями числа $x$. Делать это можно, например, с помощью дерева отрезков. Отсоритруем все запросы по $r$. Будем поддерживать в ДО на $i$-ой позиции самое правое вхождение числа $x$ левее $r$. Тогда MEX на отрезке $[l; r]$ равен минимальной позиции в ДО такой, что элемент на ней меньше $l$. Такую позицию можно найти двоичным спуском за $O(log (n))$. Асимптотика: $O(n \cdot log(n))$ ::: # [andrewns3. Цветной граф мистера Китаюта](https://codeforces.com/group/thOWHpwJb2/contest/479788/problem/andrewns3) ::: spoiler Разбор ::: info Для каждого цвета сделаем СНМ, в котором будут все рёбра этого цвета. С помощью него можно проверять, достижимы ли вершины $a$ и $b$ с помощью определённого цвета. Для каждого запроса ($a_i, b_i$) выберем из $a_i$ и $b_i$ вершину с наименьшей степенью, переберём цвета всех выходящих из неё рёбер и проверим связность в СНМ для этих цветов. Запомним ответ на запрос ${a_i, b_i}$. Если опять приходит такой же запрос, выводим уже посчитанный ответ. Асимптотика: $O(m\sqrt{q})$. ::: ::: spoiler Доказательство ::: info Пусть $deg(v)$ - степень вершины $v$. Тогда на запрос ($a_i, b_i$) ($deg(a_i) \le deg(b_i)$) мы отвечаем за $O(deg(a))$. Тогда в худшем случае все запросы --- все возможные пары из $\sqrt{q}$ вершин с максимальной степенью. Зафиксируем вершину $b$ в паре, переберём вершину $a$. Тогда суммарное время работы для всех $a$ равно $O(\sum{deg(v)}) = O(m)$. Всего $\sqrt{q}$ возможных $a$, значит суммарное время работы --- $O(m\sqrt{q})$. ::: ::: spoiler Другой способ ::: info Пронумеруем все компоненты связности с рёбрами одного цвета. Для каждой вершины $v$ охраним $comp[v]$ --- bitset из всех компонент связности, которым принадлежит эта вершина. Тогда ответ для вершин $a$ и $b$ --- это количество единичных битов в $comp[a] \& comp[b]$. Асимптотика: $O(q\frac{m}{64})$. ::: # [chay1. Покраска вершин](https://codeforces.com/group/thOWHpwJb2/contest/479788/problem/chay1) :::spoiler Подсказка 1 :::info Не для каждого дерева может существовать хорошая раскраска. ::: :::spoiler Разбор :::info Хоршая рскраска существует только для дерева, в котором степень каждой не больше двух. Дакажем это. Пусть у нас есть вершина v со степенью $3$, связанная с вершинами $u$, $w$, $y$. Предположим цвет вершины $v – 0$, $u – 1$ , $w – 2$, в таком случаи для пути $u$, $v$, $y$ цвет y должен быть $2$, а для пути $w$, $v$, $y$ цвет $y$ должен быть $1$. Мы пришли к противоречию. Теперь, зная структуру дерева, напишем $dp[v][3][3]$, где $v –$ это текущая вершина, а остальные два измерения – цвет нашей вершины и цвет потомка. Так как два цвета одназначно задают цвет третей вершины, можно запустить $dfs$ от листа и уже зная $dp$ для потомка можем пребирать цвет текущей вершины, цвет потомка и пересчитывать dp для текущей вершины. ::: # [chay2. Очистите мультимножество](https://codeforces.com/group/thOWHpwJb2/contest/479788/problem/chay2) :::spoiler Подсказка 1 :::info Первая операция отнимает $1$ на отрезке $l$ $r$, в массиве $a$. А вторая преврашает $a_i$ в $0$. И мы хотим сделать все $a_i$ равными $0$. ::: :::spoiler Подсказка 2 :::info Eсли в какой-то момент нам выгодно делать первую оперецию, то нам выгодно её применять до тех пор, пока какя-то из $a_i$ на отрезке, не станет равной $0$. ::: :::spoiler Разбор :::info Будем рекурсивно решать задачу для отрезка, второй оперецией мы можем сделать отрезок раным нулям за длинну отркзка. Или же использую первую операцию $mi = min( a_l, a_{l + 1}, ... , a_r )$ раз, отнимем от всех $a_i$ в отрезке $l$ $r$ $mi$, после этого у нас в отрезке появились нули. Разобьём отрезок на новые, так что бы в нём не было нулей и продолжим решать так же для них. ::: # [chay3. Валера и запросы](https://codeforces.com/group/thOWHpwJb2/contest/479788/problem/chay3) :::spoiler Подсказка 1 :::info Будем решать обратную задачу ::: :::spoiler Подсказка 2 :::info Будем решть задачу офлайн ::: :::spoiler Подсказка 3 :::info Пусть для запроса у нас есть пара точек $cnt_i$ и $p_{i+1}$. Для всех таких пар $($ ещё между $0$ и $p_0$ , $p_m$ и $10^6$ $)$, мы хотим найти количество отрезков полностью находящихся между этими точками. ::: :::spoiler Разбор :::info Для каждой координаты будем хронить будем хронить множество $l$ таких, что пара для пары $l$, $r$ координата является $r$. Назавём это множество $xl$. Также в множесте $xp$ в $xp_x$ будем сохранять пару из номера запроса в которм есть $p_i$ равное $x$ а так же $p_{i - 1}$. Будем переберать $x$. В структуре которая умеет прибавлять в точке и давать сумму на отрезке( например дерево фенвика ) на позиции $l$, для отрезка $l$ $r$, $r$ которого не превосходит $x$ будем прибавлять $1$. Такие $l$ у нас хроняться в $xp_x.S$. Теперь взяв сумму на отрезке от $x$ , $xp_x.S$ мы получим количесво отрезков $l$ $r$ вложенных в отрезок который образуют соседние точки, прибывим их в $ans_{xp_x.F}$. Тогда ответ на запрос $i$ – $n - ans_i$. ::: # [rubbish1. O(-1)](https://codeforces.com/group/VoWcdqCMy2/contest/479870/problem/rubbish1) :::spoiler Подсказка 1 :::info Простые числа встречаются довольно часто. Если $x$ до $10^9$, то гарантируется, что уже через 200 (возможно, даже меньше) чисел после $x$ вы найдёте хотя бы одно простое. ::: :::spoiler Подсказка 2 :::info Наибольший делитель числа $x$ равен $\frac{x}{min}$, где $min$ - минимальный делитель $x$. За $\sqrt{n}$ искать делитель слишком долго. Думайте. ::: :::spoiler Подсказка 3 :::info Во втором запросе используется решето за линию. ::: :::spoiler Разбор :::info Простые числа встречаются довольно часто. Если $x$ до $10^9$, то гарантируется, что уже через 200 (возможно, даже меньше) чисел после $x$ вы найдёте хотя бы одно простое. Так что при ответе на первый запрос достаточно перебирать числа, начиная с $x$, пока не найдём простое. Проверка числа на простоту работает за $O(\sqrt{x})$. Запросов первого типа не более тысячи, так что это работает быстро. Наибольший делитель числа $x$ равен $x/min$, где $min$ - минимальный делитель $x$. За $\sqrt{n}$ искать делитель слишком долго. Так как во втором запросе число $x$ до $10^7$, воспользуемся решетом за линию. В полученном в нём массиве $lp$ будет находиться наименьший делитель числа. В итоге, ответ равен $\frac{x}{lp_x}$. Асимптотика: $O(q \cdot \sqrt{x})$. ::: # [rubbish3. Размещения](https://codeforces.com/group/VoWcdqCMy2/contest/479870/problem/rubbish3) :::spoiler Подсказка 1 :::info Вспомните алгоритм нахождения перестановки по номеру. ::: :::spoiler Подсказка 2 :::info Предположим, мы уже собрали какой-то префикс ответа. Давайте переберём в порядке возрастания следующее число, которое мы хотим поставить. Если для нового префикса количество размещений с таким префиксом превышает текущий $y$, то число подошло, а иначе отнимем от $y$ количество размещений и попробуем поставить следующее число. Если мы так и не смогли найти число, то мы не сможем найти ответ (выведем "The times have changed"). Осталось найти количество размещений на оставшемся суффиксе массива с заданным префиксом. ::: :::spoiler Подсказка 3 :::info $n \le 16$, значит, скорее всего, это ДП по маскам. Придумаем довольно несложное решение, которое не зайдёт по TL: будем поддерживать в состоянии числа на суффиксе, которые мы уже поставили. Тогда при переходе нужно перебрать позицию, поставить новое число и проверить, соблюдаются ли все условия. Как можно маской заменить в состоянии числа в суффиксе? ::: :::spoiler Разбор :::info Предположим, мы уже собрали какой-то префикс ответа. Давайте переберём в порядке возрастания следующее число, которое мы хотим поставить. Если для нового префикса количество размещений с таким префиксом превышает текущий $y$, то число подошло, а иначе отнимем от $y$ количество размещений и попробуем поставить следующее число. Если мы так и не смогли найти число, то мы не сможем найти ответ (выведем "The times have changed"). Осталось найти количество размещений на оставшемся суффиксе массива с заданным префиксом. Выпишем отдельно числа, которые мы еще не поставили в массиве. Затем применим ДП по маскам. $dp_{mask}$ - количество способов поставить $kbits$ первых непоставленных чисел на позиции единичных битов в маске ($kbits$ - кол-во единичных битов в маске). Для перехода будем для маски перебирать позицию с нулевым битом, ставить туда следующее по возрастанию непоставленное число, и проверять, что все условия выполняются. Как это сделать? Если наша текущая позиция связана с префиксом, просто проверим, верно ли неравенство, так как числа на префиксе мы уже знаем. Если текущая позиция связана с позицией на суффиксе с нулевым битом, проигнорируем это (учтётся в дальнейшем). Если же текущая позиция связана с позицией на суффиксе с единичным битом, то текущее число ВСЕГДА будет больше связанного с ним, так как мы расставляем числа в порядке возрастания. Так как при увеличении префикса на 1 кол-во измерений в ДП уменьшается вдвое (один бит пропадает), то асимптотика будет меньше, чем изначально кажется - $O(n \cdot 2^n \cdot (n + m))$ ::: :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ :::spoiler НЕ НАЖИМАТЬ ![](https://hackmd.io/_uploads/ByMhk6ifa.jpg) ![](https://hackmd.io/_uploads/BkQFgTof6.jpg) ![](https://hackmd.io/_uploads/H1dFeTozp.jpg)