Всем Привет!↵
↵
↵
↵
Меня зовут Максим и я очень давно хочу достичь рейтинга 3000. Я верю, что для этого мне надо научиться мыслить, как человек, у которого уже есть 3000 рейтинга. Очень часто в разборах пишут фразы "заметим, что..." или "докажем вот такой факт..." и дальше идет долгое доказательство этого факта. А то, каким образом я должен к этому факту прийти, как эта мысль должна зародиться у меня в голове, никто нигде не пишет. Я думаю, что не только у меня есть эта проблема, поэтому вместо того, чтобы ждать понятный разбор, я решил начать с себя. Именно поэтому, я решил написать свой первый пошаговый разбор, где я буду описывать ход своих мыслей и действий, которые позволяют мне придумать эти самые идеи.↵
↵
Также, я создал группу по прокачке навыков спортивного программирования для людей с рейтингом 1200- , чтобы помочь им стать лучше и достигнуть рейтинга 1500+. Если хотите больше об этом узнать, рекомендую прочитать [ЭТОТ ПОСТ](https://codeforces.me/blog/entry/153213) или заполнить [ФОРМУ](https://forms.yandex.ru/u/69ea4ba0493639794fd019d8). Эту группу я назвал **Polaris** в честь путеводной звезды. В Polaris ребята решают специально подобранные контесты под их уровень, дорешивают их с помощью пошаговых разборов, изучают новую теорию, решают специально подготовленные для них подводящие упражнения, а также получают подробные рекомендации на основе их участия в тренировочных контестах. Более того, специально для участников группы я делаю пошаговые разборы тех задач, которые интересны самим участникам. Также, в группе регулярно ведется обсуждение прошедших контестов, а в ближайшем будущем мы будем готовиться к предстоящим олимпиадам (как школьным, так и студенческим). Присоединяйтесь, я буду вам очень рад!↵
↵
А теперь перейдем к самому разбору контеста. Но перед этим, я бы хотел ввести несколько правил чтения разбора для того, чтобы вы смогли получить максимум пользы от него.↵
↵
1. Перед чтением разбора задачи, убедитесь, что вы прочитали задачу, подумали над ней, извлекли из своей головы и записали/нарисовали максимальное количество идей и больше уже ничего не можете придумать.↵
2. Во время чтения разбора, если в какой-то момент, какое-то предложение в разборе навело вас на новую мысль, перестаньте читать разбор и вернитесь к пункту (1), а именно продолжите с этого места генерировать новые идеи. Это очень важно.↵
3. Если вы дочитали текст разбора до конца и не поняли, как решать задачу или остались вопросы, то их нужно обязательно задать в комментариях или спросить в Polaris. Там вам помогут я и ребята, кто справился с этой задачей. Также в этом случае, полезно прочитать код, который будет прикреплен к разбору.↵
4. После того, как вы решили задачу, обязательно посмотрите код других участников и код с разбора. Возможно, он наведет вас на мысль о том, как можно было проще и быстрее реализовать решение задачи.↵
↵
A. Евклид, последовательность, два числа↵
===================↵
↵
<spoiler summary="Шаг 1">↵
Как строится последовательность $a$? В условии написано, что $a_{i+2}=a_{i}\mod a_{i+1}$ Каким свойством тогда должна обладать последовательность $a$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 2">↵
По построению, получается, что $a_i \ge a_{i+1}$, то есть последовательность должна быть отсортирована по невозрастанию. Как тогда решать всю задачу?↵
</spoiler>↵
↵
<spoiler summary="Шаг 3">↵
Тогда мы можем отсортировать последовательность $b$ по невозрастанию и проверить, что $b_{i+2}=b_{i}\mod b_{i+1}$↵
</spoiler>↵
↵
Решение: [submission:377783495]↵
↵
B. Палиндром, двенадцать, два слагаемых↵
===================↵
↵
<spoiler summary="Шаг 1">↵
Какие самые простые числа являются палиндромами?↵
</spoiler>↵
↵
<spoiler summary="Шаг 2">↵
Это числа, состоящие из одной цифры. Когда мы можем так сделать? Как мы можем использовать свойство числа $b$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 3">↵
Мы знаем, что число $b$ делится на $12$, тогда $b = (n - a)$ тоже делится на $12$. Тогда что мы знаем про число $a$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 4">↵
Мы знаем остаток от деления числа $a$ на $12$, он равен остатку от деления числа $n$ на $12$, потому что $n-a\equiv\pmod{12}$, значит $n\equiv a\pmod{12}$. Пусть $r$ — остаток от деления. Тогда какие числа мы можем использовать в качестве числа $a$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 5">↵
$a \in \{r, r + 12, r + 24, r + 36, \ldots, r + 12\cdot i, \ldots\}$. Что если $r < 10$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 6">↵
Тогда мы можем взять $a = r$, потому что число $a$ в таком случае будет состоять из одной цифры. А что если $r \in \{10, 11\}$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 7">↵
Если $r = 11$, то опять можем взять $a = r = 11$, потому что $11$ уже палиндром. Остался случай $r = 10$. Что делать с ним?↵
</spoiler>↵
↵
<spoiler summary="Шаг 8">↵
Если $r = 10$, тогда $a \in \{10, 22, 34, 46, \ldots}$. Какое $a$ можем взять?↵
</spoiler>↵
↵
<spoiler summary="Шаг 9">↵
Можем взять $a = 22$. На самом деле, теперь мы видим, что если ответ есть, то можем выбрать $a \le 22$, тогда можем просто перебрать $a$ и проверить, что $(n - a)\equiv 0\pmod{12}$ и $a$ палиндром.↵
</spoiler>↵
↵
Решение: [submission:377783904]↵
↵
C. Сосуды, высоты, две версии (простая версия)↵
===================↵
↵
<spoiler summary="Шаг 1">↵
Первое, на что я обратил внимание — это ограничения. Они позволяют решить задачу за $O(n^2)$, тогда мы можем для каждого $i$ решить задачу за $O(n)$.↵
</spoiler>↵
↵
<spoiler summary="Шаг 2">↵
Давайте разберем случай, когда $i=1$, тогда остальные можно решить аналогично. Итак, мы хотим, чтобы $w_1=0$, а также чтобы выполнялись условия сообщающихся сосудов. Сейчас в задаче циклическое условие, какую более простую задачу можно решить?↵
</spoiler>↵
↵
<spoiler summary="Шаг 3">↵
Можно попробовать решить задачу, где наше условие не цикличное. Как это сделать?↵
</spoiler>↵
↵
<spoiler summary="Шаг 4">↵
Как выбрать $w_2$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 5">↵
Можно взять $w_2=h_2$, но тогда возможно сломается условие для $h_2$. Как выбрать $w_3$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 6">↵
Можем взять $w_3 = \max(w_2,h_2)$, тогда что будет если $w_2 > h_2$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 7">↵
Тогда $w_3 = w_2$ и условие сохранилось, тогда как выбрать $w_{i+1}$, если мы знаем $w_i$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 8">↵
Можем взять $w_{i+1}=\max(w_i, h_i)$. То есть по сути мы строим массив префиксных максимумов массива $h$. Что в таком случае у нас ломается?↵
</spoiler>↵
↵
<spoiler summary="Шаг 9">↵
Сломаться может условие на $h_n$, потому что в исходной задаче мы имеет цикличные условия. То есть может быть так, что $w_n$ слишком большой, а т.к. $w_1=0$, то возможно, что $w_n > h_n$ и $w_n\neq w_1$. Как будет выглядеть наш полученный массив $w$? На какой элемент в массиве $h$ можно обратить внимание?↵
</spoiler>↵
↵
<spoiler summary="Шаг 10">↵
На максимальный элемент, пусть он расположен в $h_q$. После $q$-го элемента все элементы будут равны. Какой аналогичный простой шаг мы можем сделать?↵
</spoiler>↵
↵
<spoiler summary="Шаг 11">↵
Мы можем построить массив суффиксных максимумов, тогда возможно сломается условие на $h_1$ из-за того, что $w_2$ будет слишком большим. Как мы можем тогда решить задачу?↵
</spoiler>↵
↵
<spoiler summary="Шаг 12">↵
В качестве финального $w$ мы можем взять минимум из двух ответов — префиксного максимума и суффиксного максимума.↵
</spoiler>↵
↵
Решение: [submission:377786075]↵
↵
D. Ксор, выражение, два бинарных числа↵
===================↵
↵
<spoiler summary="Шаг 1">↵
Попробую проэмулировать несколько первых шагов. Изначально нам известны числа на позициях $\{1, 2^k+1\}$, после первого шага нам будут известны числа на позициях $\{1, 2^{k-1}+1, 2^k+1\}$. Что будет еще на следующем шаге?↵
</spoiler>↵
↵
<spoiler summary="Шаг 2">↵
Нам будут известны числа на позициях $\{1, 2^{k-2}+1,2^{k-1}+1,2^{k-2}+2^{k-1}+1\}$. Чем равно расстояние между соседними индексами?↵
</spoiler>↵
↵
<spoiler summary="Шаг 3">↵
До шагов расстояние равно $2^k+1-1=2^k$, на первом шаге расстояние равно $2^{k-1}+1-1=2^k+1-(2^{k-1}+1)=2^{k-1}$. Какое будет расстояние между индексами на следующем шаге?↵
</spoiler>↵
↵
<spoiler summary="Шаг 4">↵
Оно будет равно $2^{k-2}$ и так далее. Мы хотим посчитать $\sum_i x_i\cdot y_i$, как можно вычислить $y_i$, зная только $x_i$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 5">↵
Можно вычислить так: $y_i = n - x_i$, тогда вся сумма будет равна $n\sum_i x_i - \left(\sum_i x_i^2\right)$. Как вычислить $\sum_i x_i$? Какой физический смысл у этой суммы?↵
</spoiler>↵
↵
<spoiler summary="Шаг 6">↵
Эта сумма считает общее количество бит по всем элементам массив, можно ли это как-то перефразировать?↵
</spoiler>↵
↵
<spoiler summary="Шаг 7">↵
Пусть $F(j)$ — количество элементов в массиве $a$, у которых $j$-й бит равен единице? Тогда чему равна вся сумма?↵
</spoiler>↵
↵
<spoiler summary="Шаг 8">↵
Вся сумма равна $\sum_j F(j)$. Как посчитать $F(j)$ для конкретного $j$? От чего зависит эта величина?↵
</spoiler>↵
↵
<spoiler summary="Шаг 9">↵
Эта величина зависит от того, что находится в $j$-м бите у чисел $a_1, a_{2^k+1}$. И размера массива.↵
</spoiler>↵
↵
<spoiler summary="Шаг 10">↵
Такую величину можно посчитать с помощью динамического программирования $F_{l, x, y}$ -- количество ежиниц в массиве $a$, если этот массив будет состоять из $2^l+1$ элементов, а первый и последний элемент будут равны $x$ и $y$ соответственно. Какая База динамики?↵
</spoiler>↵
↵
<spoiler summary="Шаг 11">↵
База динамики такая: $F_{0,x,y}=x+y$. А где будет лежать ответ?↵
</spoiler>↵
↵
<spoiler summary="Шаг 12">↵
Пусть $cnt_{x,y}$ — количество бит, что в $a_1$ лежит бит $x$, а в $a_{2^k+1}$ лежит бит $y$. Тогда $\sum_i x_i = \sum_{x=0}^{1}\sum_{y=0}^{1}cnt_{x,y}\cdot F_{k,x,y}$. Осталось только посчитать переход динамики.↵
</spoiler>↵
↵
<spoiler summary="Шаг 13">↵
Допустим, мы знаем ответ для слоя $l$, то есть знаем значения $F_{l,x,y}$ для любых $x,y$. Как посчитать $F_{l+1,x,y}$? Мы знаем, что мы должны рассмотреть середину и положить туда число $z=x\oplus y$↵
</spoiler>↵
↵
<spoiler summary="Шаг 14">↵
Тогда $F_{l+1,x,y}=F_{l,x,z}+F_{l,z,y}-z$, потому что мы поделим массив на две части и два раз посчитаем $z$, поэтому его нужно один раз вычесть из ответа.↵
</spoiler>↵
↵
<spoiler summary="Шаг 15">↵
Хорошо, как теперь посчитать $\sum_i x_i^2$? Какой физический смысл этой величины?↵
</spoiler>↵
↵
<spoiler summary="Шаг 16">↵
Физический смысл этой величины такой: по сути мы перебираем все пары бит $p,q$ и добавляем единицу, если в $p$-м бите и в $q$-м бите стоят единицы. Как тогда это посчитать?↵
</spoiler>↵
↵
<spoiler summary="Шаг 17">↵
Опять с помощью динамики $G_{l,x,y,z,w}$ — это количество элементов финального массива (причем все элементы состоят из двух бит), что в этих элементах в обоих битах стоят единицы. Причем первый элемент содержит биты $\{x,y\}$, а последний элемент содержит биты $\{z,w\}$. Какая база динамики?↵
</spoiler>↵
↵
<spoiler summary="Шаг 18">↵
База динамики: $G_{0,x,y,z,w}=xy+zw$. А как посчитать ответ?↵
</spoiler>↵
↵
<spoiler summary="Шаг 19">↵
Ответ можно посчитать так: $\sum_i x_i^2 = \sum_{x=0}^{1}\sum_{y=0}^{1}\sum_{z=0}^{1}\sum_{w=0}^{1}cnt_{x,z}\cdot cnt_{y,w}\cdot G_{k,x,y,z,w}$. Осталось только разобраться с переходом.↵
</spoiler>↵
↵
<spoiler summary="Шаг 20">↵
Мы хотим найти $G_{l+1}$ по $G_l$. Оять мы выделяем середину, в которой будут лежать биты $\{u=x\oplus z, v=y\oplus w\}$. Тогда $G_{l+1,x,y,z,w}=G_{l,x,y,u,v}+G_{l,u,v,z,w}-u\cdot v$.↵
</spoiler>↵
↵
Решение: [submission:377789921]↵
↵
E. Влад, Миша, два массива↵
===================↵
↵
<spoiler summary="Шаг 1">↵
Итак, мы знаем, что $a_i$ — количество отрезков, в которых $p_i$ является минимумом. Представим, что мы смотрим на какую-то перестановку, на какой элемент можно обратить внимание?↵
</spoiler>↵
↵
<spoiler summary="Шаг 2">↵
На минимальный элемент, пусть он находится в позиции $i$, тогда сколько отрезков его покрывает?↵
</spoiler>↵
↵
<spoiler summary="Шаг 3">↵
Его покрывает $i\cdot (n-i+1)$ (в 1-индексации). Как нам найти позицию, где лежит минимумум? А что если их несколько?↵
</spoiler>↵
↵
<spoiler summary="Шаг 4">↵
Все позиции, где $a_i=i\cdot(n-i+1)$ потенциальные позиции для минимума. Если таких нет, то ответ 0, а если их несколько? Тогда ответ тоже 0, потому что в перестановке только один минимум. Хорошо, тогда пусть мы смогли найти позицию минимума $i$. Тогда левее этого элемента находится $c_l=i-1$ элементов, а правее $c_r=n-i$. Зависят ли элементы из левой части от элементов из правой части?↵
</spoiler>↵
↵
<spoiler summary="Шаг 5">↵
Не завсият, тогда мы можем распределить осташивеся $(n-1)$ элементов по этим частям любым способом и рекурсивно решить задачу для обеих частей. Сколько есть способов распределить $(n-1)$ элементов по обеим частям?↵
</spoiler>↵
↵
<spoiler summary="Шаг 6">↵
Всего есть $\binom{c_l+c_r}{c_l}$ способов. Если количество перестановок в левой части равно $L$, а в правой часте равно $R$, тогда чему равен итоговый ответ?↵
</spoiler>↵
↵
<spoiler summary="Шаг 7">↵
Он равен $\binom{c_l+c_r}{c_l}\cdot L\cdot R$. Осталось только понять, как находить минимальный иднекс $i$? Что будет если мы каждый раз будем находить его ближе к конце массива, какое время работы будет в худшем случае?↵
</spoiler>↵
↵
<spoiler summary="Шаг 8">↵
Оно будет равно $n+(n-1)+(n-2)+\ldots + 1=O(n^2)$. А если мы будм находить его всегда в $i \le n / 2$.↵
</spoiler>↵
↵
<spoiler summary="Шаг 9">↵
Тогда время работы можно оценить так $T(n)=T(c_l)+T(c_r)+\min(c_l,c_r) \le 2T(n/2)+O(n)=O(n\log{n})$. Это называется [мастер-теорема](https://neerc.ifmo.ru/wiki/index.php?title=%D0%9C%D0%B0%D1%81%D1%82%D0%B5%D1%80-%D1%82%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0)↵
</spoiler>↵
↵
Решение: [submission:377791711]↵
↵
F. Сосуды, высоты, две версии (сложная версия)↵
===================↵
↵
<spoiler summary="Шаг 1">↵
Из задачи $C$ мы знаем, что для каждого $i$ мы ищем префиксные и суффиксные максимумы и считаем сумму минимумов из двух ответов. Чтобы удобнее было работать, давайте удвоим массив $h$, то есть увеличим его в два раза и сделаем $h_{i+n}=h_i$. Тогда при работе с ответов для $i$-го индекса нам нужно будет решать задачу для подотрезка $[i, i + n)$. В каком месте префиксные максимумы перестают меняться?↵
</spoiler>↵
↵
<spoiler summary="Шаг 2">↵
Префиксные максимумы, как и суффиксные перестают меняться в максимамльном элементе $h_q$. Как его быстро найти для всех подотрезков $[i, i + n)$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 3">↵
Пусть $h_z$ — первый максимум во всем массиве $h$, тогда $q = z$ или $q = z + n$. Тогда по сути нам нужно стартонуть с элемента $i$ и идти до элемента $q$, поддерживая максимум и считая сумму этих максимумов. Аналогично, нам нужно стартонуть с элемента $i + n - 1$ и идти до $q$, поддерживая максимум. Тогда нам нужно научиться для массива $h$ и индекса $q$ считать массив $R_j,j \ge q$ — сумма максимумов, если мы начнем с $j$-го элемента и будем идти до элемента $q$. Как можно это сделать?↵
</spoiler>↵
↵
<spoiler summary="Шаг 4">↵
Для начала можно сделать $R_j=R_{j-1}+h_j$, но тогда мы упустим ответ, если $h_j > h_{j-1}$. На какой элемент слева от $j$ нам нужно смотреть?↵
</spoiler>↵
↵
<spoiler summary="Шаг 5">↵
Нам нужно найти ближайший слева элемент $v < j$, что $h_v \ge h_j$, тогда чему будет равен $R_j$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 6">↵
Он будет равен $R_j=R_{v}+(j-v)\cdot h_j$. Как найти $v$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 7">↵
С помощью стека, будем идти слева направо и поддерживать некоторое множество индексов. Пусть мы рассматриваем индекс $j$, тогда нам нужно снять с вершины стека все индекс, значения в которых меньше $h_j$, тогда после этого на вершине стека будет как раз ближайший слева элемент $h_v \ge h_j$.↵
</spoiler>↵
↵
Решение: [submission:377799821]
↵
↵
↵
Меня зовут Максим и я очень давно хочу достичь рейтинга 3000. Я верю, что для этого мне надо научиться мыслить, как человек, у которого уже есть 3000 рейтинга. Очень часто в разборах пишут фразы "заметим, что..." или "докажем вот такой факт..." и дальше идет долгое доказательство этого факта. А то, каким образом я должен к этому факту прийти, как эта мысль должна зародиться у меня в голове, никто нигде не пишет. Я думаю, что не только у меня есть эта проблема, поэтому вместо того, чтобы ждать понятный разбор, я решил начать с себя. Именно поэтому, я решил написать свой первый пошаговый разбор, где я буду описывать ход своих мыслей и действий, которые позволяют мне придумать эти самые идеи.↵
↵
Также, я создал группу по прокачке навыков спортивного программирования для людей с рейтингом 1200- , чтобы помочь им стать лучше и достигнуть рейтинга 1500+. Если хотите больше об этом узнать, рекомендую прочитать [ЭТОТ ПОСТ](https://codeforces.me/blog/entry/153213) или заполнить [ФОРМУ](https://forms.yandex.ru/u/69ea4ba0493639794fd019d8). Эту группу я назвал **Polaris** в честь путеводной звезды. В Polaris ребята решают специально подобранные контесты под их уровень, дорешивают их с помощью пошаговых разборов, изучают новую теорию, решают специально подготовленные для них подводящие упражнения, а также получают подробные рекомендации на основе их участия в тренировочных контестах. Более того, специально для участников группы я делаю пошаговые разборы тех задач, которые интересны самим участникам. Также, в группе регулярно ведется обсуждение прошедших контестов, а в ближайшем будущем мы будем готовиться к предстоящим олимпиадам (как школьным, так и студенческим). Присоединяйтесь, я буду вам очень рад!↵
↵
А теперь перейдем к самому разбору контеста. Но перед этим, я бы хотел ввести несколько правил чтения разбора для того, чтобы вы смогли получить максимум пользы от него.↵
↵
1. Перед чтением разбора задачи, убедитесь, что вы прочитали задачу, подумали над ней, извлекли из своей головы и записали/нарисовали максимальное количество идей и больше уже ничего не можете придумать.↵
2. Во время чтения разбора, если в какой-то момент, какое-то предложение в разборе навело вас на новую мысль, перестаньте читать разбор и вернитесь к пункту (1), а именно продолжите с этого места генерировать новые идеи. Это очень важно.↵
3. Если вы дочитали текст разбора до конца и не поняли, как решать задачу или остались вопросы, то их нужно обязательно задать в комментариях или спросить в Polaris. Там вам помогут я и ребята, кто справился с этой задачей. Также в этом случае, полезно прочитать код, который будет прикреплен к разбору.↵
4. После того, как вы решили задачу, обязательно посмотрите код других участников и код с разбора. Возможно, он наведет вас на мысль о том, как можно было проще и быстрее реализовать решение задачи.↵
↵
A. Евклид, последовательность, два числа↵
===================↵
↵
<spoiler summary="Шаг 1">↵
Как строится последовательность $a$? В условии написано, что $a_{i+2}=a_{i}\mod a_{i+1}$ Каким свойством тогда должна обладать последовательность $a$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 2">↵
По построению, получается, что $a_i \ge a_{i+1}$, то есть последовательность должна быть отсортирована по невозрастанию. Как тогда решать всю задачу?↵
</spoiler>↵
↵
<spoiler summary="Шаг 3">↵
Тогда мы можем отсортировать последовательность $b$ по невозрастанию и проверить, что $b_{i+2}=b_{i}\mod b_{i+1}$↵
</spoiler>↵
↵
Решение: [submission:377783495]↵
↵
B. Палиндром, двенадцать, два слагаемых↵
===================↵
↵
<spoiler summary="Шаг 1">↵
Какие самые простые числа являются палиндромами?↵
</spoiler>↵
↵
<spoiler summary="Шаг 2">↵
Это числа, состоящие из одной цифры. Когда мы можем так сделать? Как мы можем использовать свойство числа $b$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 3">↵
Мы знаем, что число $b$ делится на $12$, тогда $b = (n - a)$ тоже делится на $12$. Тогда что мы знаем про число $a$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 4">↵
Мы знаем остаток от деления числа $a$ на $12$, он равен остатку от деления числа $n$ на $12$, потому что $n-a\equiv\pmod{12}$, значит $n\equiv a\pmod{12}$. Пусть $r$ — остаток от деления. Тогда какие числа мы можем использовать в качестве числа $a$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 5">↵
$a \in \{r, r + 12, r + 24, r + 36, \ldots, r + 12\cdot i, \ldots\}$. Что если $r < 10$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 6">↵
Тогда мы можем взять $a = r$, потому что число $a$ в таком случае будет состоять из одной цифры. А что если $r \in \{10, 11\}$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 7">↵
Если $r = 11$, то опять можем взять $a = r = 11$, потому что $11$ уже палиндром. Остался случай $r = 10$. Что делать с ним?↵
</spoiler>↵
↵
<spoiler summary="Шаг 8">↵
Если $r = 10$, тогда $a \in \{10, 22, 34, 46, \ldots}$. Какое $a$ можем взять?↵
</spoiler>↵
↵
<spoiler summary="Шаг 9">↵
Можем взять $a = 22$. На самом деле, теперь мы видим, что если ответ есть, то можем выбрать $a \le 22$, тогда можем просто перебрать $a$ и проверить, что $(n - a)\equiv 0\pmod{12}$ и $a$ палиндром.↵
</spoiler>↵
↵
Решение: [submission:377783904]↵
↵
C. Сосуды, высоты, две версии (простая версия)↵
===================↵
↵
<spoiler summary="Шаг 1">↵
Первое, на что я обратил внимание — это ограничения. Они позволяют решить задачу за $O(n^2)$, тогда мы можем для каждого $i$ решить задачу за $O(n)$.↵
</spoiler>↵
↵
<spoiler summary="Шаг 2">↵
Давайте разберем случай, когда $i=1$, тогда остальные можно решить аналогично. Итак, мы хотим, чтобы $w_1=0$, а также чтобы выполнялись условия сообщающихся сосудов. Сейчас в задаче циклическое условие, какую более простую задачу можно решить?↵
</spoiler>↵
↵
<spoiler summary="Шаг 3">↵
Можно попробовать решить задачу, где наше условие не цикличное. Как это сделать?↵
</spoiler>↵
↵
<spoiler summary="Шаг 4">↵
Как выбрать $w_2$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 5">↵
Можно взять $w_2=h_2$, но тогда возможно сломается условие для $h_2$. Как выбрать $w_3$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 6">↵
Можем взять $w_3 = \max(w_2,h_2)$, тогда что будет если $w_2 > h_2$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 7">↵
Тогда $w_3 = w_2$ и условие сохранилось, тогда как выбрать $w_{i+1}$, если мы знаем $w_i$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 8">↵
Можем взять $w_{i+1}=\max(w_i, h_i)$. То есть по сути мы строим массив префиксных максимумов массива $h$. Что в таком случае у нас ломается?↵
</spoiler>↵
↵
<spoiler summary="Шаг 9">↵
Сломаться может условие на $h_n$, потому что в исходной задаче мы имеет цикличные условия. То есть может быть так, что $w_n$ слишком большой, а т.к. $w_1=0$, то возможно, что $w_n > h_n$ и $w_n\neq w_1$. Как будет выглядеть наш полученный массив $w$? На какой элемент в массиве $h$ можно обратить внимание?↵
</spoiler>↵
↵
<spoiler summary="Шаг 10">↵
На максимальный элемент, пусть он расположен в $h_q$. После $q$-го элемента все элементы будут равны. Какой аналогичный простой шаг мы можем сделать?↵
</spoiler>↵
↵
<spoiler summary="Шаг 11">↵
Мы можем построить массив суффиксных максимумов, тогда возможно сломается условие на $h_1$ из-за того, что $w_2$ будет слишком большим. Как мы можем тогда решить задачу?↵
</spoiler>↵
↵
<spoiler summary="Шаг 12">↵
В качестве финального $w$ мы можем взять минимум из двух ответов — префиксного максимума и суффиксного максимума.↵
</spoiler>↵
↵
Решение: [submission:377786075]↵
↵
D. Ксор, выражение, два бинарных числа↵
===================↵
↵
<spoiler summary="Шаг 1">↵
Попробую проэмулировать несколько первых шагов. Изначально нам известны числа на позициях $\{1, 2^k+1\}$, после первого шага нам будут известны числа на позициях $\{1, 2^{k-1}+1, 2^k+1\}$. Что будет еще на следующем шаге?↵
</spoiler>↵
↵
<spoiler summary="Шаг 2">↵
Нам будут известны числа на позициях $\{1, 2^{k-2}+1,2^{k-1}+1,2^{k-2}+2^{k-1}+1\}$. Чем равно расстояние между соседними индексами?↵
</spoiler>↵
↵
<spoiler summary="Шаг 3">↵
До шагов расстояние равно $2^k+1-1=2^k$, на первом шаге расстояние равно $2^{k-1}+1-1=2^k+1-(2^{k-1}+1)=2^{k-1}$. Какое будет расстояние между индексами на следующем шаге?↵
</spoiler>↵
↵
<spoiler summary="Шаг 4">↵
Оно будет равно $2^{k-2}$ и так далее. Мы хотим посчитать $\sum_i x_i\cdot y_i$, как можно вычислить $y_i$, зная только $x_i$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 5">↵
Можно вычислить так: $y_i = n - x_i$, тогда вся сумма будет равна $n\sum_i x_i - \left(\sum_i x_i^2\right)$. Как вычислить $\sum_i x_i$? Какой физический смысл у этой суммы?↵
</spoiler>↵
↵
<spoiler summary="Шаг 6">↵
Эта сумма считает общее количество бит по всем элементам массив, можно ли это как-то перефразировать?↵
</spoiler>↵
↵
<spoiler summary="Шаг 7">↵
Пусть $F(j)$ — количество элементов в массиве $a$, у которых $j$-й бит равен единице? Тогда чему равна вся сумма?↵
</spoiler>↵
↵
<spoiler summary="Шаг 8">↵
Вся сумма равна $\sum_j F(j)$. Как посчитать $F(j)$ для конкретного $j$? От чего зависит эта величина?↵
</spoiler>↵
↵
<spoiler summary="Шаг 9">↵
Эта величина зависит от того, что находится в $j$-м бите у чисел $a_1, a_{2^k+1}$. И размера массива.↵
</spoiler>↵
↵
<spoiler summary="Шаг 10">↵
Такую величину можно посчитать с помощью динамического программирования $F_{l, x, y}$ -- количество ежиниц в массиве $a$, если этот массив будет состоять из $2^l+1$ элементов, а первый и последний элемент будут равны $x$ и $y$ соответственно. Какая База динамики?↵
</spoiler>↵
↵
<spoiler summary="Шаг 11">↵
База динамики такая: $F_{0,x,y}=x+y$. А где будет лежать ответ?↵
</spoiler>↵
↵
<spoiler summary="Шаг 12">↵
Пусть $cnt_{x,y}$ — количество бит, что в $a_1$ лежит бит $x$, а в $a_{2^k+1}$ лежит бит $y$. Тогда $\sum_i x_i = \sum_{x=0}^{1}\sum_{y=0}^{1}cnt_{x,y}\cdot F_{k,x,y}$. Осталось только посчитать переход динамики.↵
</spoiler>↵
↵
<spoiler summary="Шаг 13">↵
Допустим, мы знаем ответ для слоя $l$, то есть знаем значения $F_{l,x,y}$ для любых $x,y$. Как посчитать $F_{l+1,x,y}$? Мы знаем, что мы должны рассмотреть середину и положить туда число $z=x\oplus y$↵
</spoiler>↵
↵
<spoiler summary="Шаг 14">↵
Тогда $F_{l+1,x,y}=F_{l,x,z}+F_{l,z,y}-z$, потому что мы поделим массив на две части и два раз посчитаем $z$, поэтому его нужно один раз вычесть из ответа.↵
</spoiler>↵
↵
<spoiler summary="Шаг 15">↵
Хорошо, как теперь посчитать $\sum_i x_i^2$? Какой физический смысл этой величины?↵
</spoiler>↵
↵
<spoiler summary="Шаг 16">↵
Физический смысл этой величины такой: по сути мы перебираем все пары бит $p,q$ и добавляем единицу, если в $p$-м бите и в $q$-м бите стоят единицы. Как тогда это посчитать?↵
</spoiler>↵
↵
<spoiler summary="Шаг 17">↵
Опять с помощью динамики $G_{l,x,y,z,w}$ — это количество элементов финального массива (причем все элементы состоят из двух бит), что в этих элементах в обоих битах стоят единицы. Причем первый элемент содержит биты $\{x,y\}$, а последний элемент содержит биты $\{z,w\}$. Какая база динамики?↵
</spoiler>↵
↵
<spoiler summary="Шаг 18">↵
База динамики: $G_{0,x,y,z,w}=xy+zw$. А как посчитать ответ?↵
</spoiler>↵
↵
<spoiler summary="Шаг 19">↵
Ответ можно посчитать так: $\sum_i x_i^2 = \sum_{x=0}^{1}\sum_{y=0}^{1}\sum_{z=0}^{1}\sum_{w=0}^{1}cnt_{x,z}\cdot cnt_{y,w}\cdot G_{k,x,y,z,w}$. Осталось только разобраться с переходом.↵
</spoiler>↵
↵
<spoiler summary="Шаг 20">↵
Мы хотим найти $G_{l+1}$ по $G_l$. Оять мы выделяем середину, в которой будут лежать биты $\{u=x\oplus z, v=y\oplus w\}$. Тогда $G_{l+1,x,y,z,w}=G_{l,x,y,u,v}+G_{l,u,v,z,w}-u\cdot v$.↵
</spoiler>↵
↵
Решение: [submission:377789921]↵
↵
E. Влад, Миша, два массива↵
===================↵
↵
<spoiler summary="Шаг 1">↵
Итак, мы знаем, что $a_i$ — количество отрезков, в которых $p_i$ является минимумом. Представим, что мы смотрим на какую-то перестановку, на какой элемент можно обратить внимание?↵
</spoiler>↵
↵
<spoiler summary="Шаг 2">↵
На минимальный элемент, пусть он находится в позиции $i$, тогда сколько отрезков его покрывает?↵
</spoiler>↵
↵
<spoiler summary="Шаг 3">↵
Его покрывает $i\cdot (n-i+1)$ (в 1-индексации). Как нам найти позицию, где лежит минимумум? А что если их несколько?↵
</spoiler>↵
↵
<spoiler summary="Шаг 4">↵
Все позиции, где $a_i=i\cdot(n-i+1)$ потенциальные позиции для минимума. Если таких нет, то ответ 0, а если их несколько? Тогда ответ тоже 0, потому что в перестановке только один минимум. Хорошо, тогда пусть мы смогли найти позицию минимума $i$. Тогда левее этого элемента находится $c_l=i-1$ элементов, а правее $c_r=n-i$. Зависят ли элементы из левой части от элементов из правой части?↵
</spoiler>↵
↵
<spoiler summary="Шаг 5">↵
Не завсият, тогда мы можем распределить осташивеся $(n-1)$ элементов по этим частям любым способом и рекурсивно решить задачу для обеих частей. Сколько есть способов распределить $(n-1)$ элементов по обеим частям?↵
</spoiler>↵
↵
<spoiler summary="Шаг 6">↵
Всего есть $\binom{c_l+c_r}{c_l}$ способов. Если количество перестановок в левой части равно $L$, а в правой часте равно $R$, тогда чему равен итоговый ответ?↵
</spoiler>↵
↵
<spoiler summary="Шаг 7">↵
Он равен $\binom{c_l+c_r}{c_l}\cdot L\cdot R$. Осталось только понять, как находить минимальный иднекс $i$? Что будет если мы каждый раз будем находить его ближе к конце массива, какое время работы будет в худшем случае?↵
</spoiler>↵
↵
<spoiler summary="Шаг 8">↵
Оно будет равно $n+(n-1)+(n-2)+\ldots + 1=O(n^2)$. А если мы будм находить его всегда в $i \le n / 2$.↵
</spoiler>↵
↵
<spoiler summary="Шаг 9">↵
Тогда время работы можно оценить так $T(n)=T(c_l)+T(c_r)+\min(c_l,c_r) \le 2T(n/2)+O(n)=O(n\log{n})$. Это называется [мастер-теорема](https://neerc.ifmo.ru/wiki/index.php?title=%D0%9C%D0%B0%D1%81%D1%82%D0%B5%D1%80-%D1%82%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0)↵
</spoiler>↵
↵
Решение: [submission:377791711]↵
↵
F. Сосуды, высоты, две версии (сложная версия)↵
===================↵
↵
<spoiler summary="Шаг 1">↵
Из задачи $C$ мы знаем, что для каждого $i$ мы ищем префиксные и суффиксные максимумы и считаем сумму минимумов из двух ответов. Чтобы удобнее было работать, давайте удвоим массив $h$, то есть увеличим его в два раза и сделаем $h_{i+n}=h_i$. Тогда при работе с ответов для $i$-го индекса нам нужно будет решать задачу для подотрезка $[i, i + n)$. В каком месте префиксные максимумы перестают меняться?↵
</spoiler>↵
↵
<spoiler summary="Шаг 2">↵
Префиксные максимумы, как и суффиксные перестают меняться в максимамльном элементе $h_q$. Как его быстро найти для всех подотрезков $[i, i + n)$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 3">↵
Пусть $h_z$ — первый максимум во всем массиве $h$, тогда $q = z$ или $q = z + n$. Тогда по сути нам нужно стартонуть с элемента $i$ и идти до элемента $q$, поддерживая максимум и считая сумму этих максимумов. Аналогично, нам нужно стартонуть с элемента $i + n - 1$ и идти до $q$, поддерживая максимум. Тогда нам нужно научиться для массива $h$ и индекса $q$ считать массив $R_j,j \ge q$ — сумма максимумов, если мы начнем с $j$-го элемента и будем идти до элемента $q$. Как можно это сделать?↵
</spoiler>↵
↵
<spoiler summary="Шаг 4">↵
Для начала можно сделать $R_j=R_{j-1}+h_j$, но тогда мы упустим ответ, если $h_j > h_{j-1}$. На какой элемент слева от $j$ нам нужно смотреть?↵
</spoiler>↵
↵
<spoiler summary="Шаг 5">↵
Нам нужно найти ближайший слева элемент $v < j$, что $h_v \ge h_j$, тогда чему будет равен $R_j$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 6">↵
Он будет равен $R_j=R_{v}+(j-v)\cdot h_j$. Как найти $v$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 7">↵
С помощью стека, будем идти слева направо и поддерживать некоторое множество индексов. Пусть мы рассматриваем индекс $j$, тогда нам нужно снять с вершины стека все индекс, значения в которых меньше $h_j$, тогда после этого на вершине стека будет как раз ближайший слева элемент $h_v \ge h_j$.↵
</spoiler>↵
↵
Решение: [submission:377799821]
