# Разбор контеста "Худшие сборы 3: теория игр и чисел"

> Дорешка по разбору - самое важное в СП. Если вы не дорешиваете, вы ничему не учитесь.

:::warning
Совет: не лезьте в разбор сразу же. В идеале, подумайте над задачей где-то 20-30 минут, и только потом читайте разбор.
:::

# [G.RETRO. Новая игра](https://codeforces.com/gym/501344/problem/G.RETRO)
:::spoiler Подсказка 1
:::info
Сделаем граф, в котором вершины - клетки нашей матрицы. Соответственно, из каждой вершины этого графа будут выходить не более двух направленных рёбер.
:::
:::spoiler Подсказка 2
:::info
Вы, возможно, будете в шоке, но для этого графа нужно применить метод ретроспективного анализа.
:::
:::spoiler Разбор
:::info
Сделаем граф, в котором вершины - клетки нашей матрицы. Соответственно, из каждой вершины этого графа будут выходить не более двух направленных рёбер. Затем, применим метод ретроспективного анализа и найдём состояние для текущей вершины и первого игрока. Если состояние выигрышное - выиграл Антон, если проигрышное - выиграл Яша, а иначе между игроками будет ничья.

Асимптотика - $O(N \cdot M)$.
:::

# [G1. Жадина-говядина](https://codeforces.com/gym/501344/problem/G1)
:::spoiler Подсказка
:::info
Какая стратегия есть у первого и второго игрока?
:::
:::spoiler Разбор
:::info
Если $n$ даёт при делении на $k+1$ остаток 1, то у второго игрока есть стратегия для выигрыша. Если первый игрок берёт на очередном ходу $x$ конфет, второй возьмёт $k+1-x$ конфет (он всегда может это сделать). Как только в кучке останется одна конфета, её возьмёт первый игрок и проиграет.

Если $n$ не даёт при делении на $k+1$ остаток 1, первый игрок своим ходом всегда может свести игру к остатку 1, и соответственно, он выиграет.

Асимптотика: $O(1)$ для каждого тестового случая.
:::

# [G2. Шоколадка Г2](https://codeforces.com/gym/501344/problem/G2)
:::spoiler Подсказка
:::info
В этой задаче используется теорема Шпрага-Гранди. Пусть $g[i][j]$ - число Гранди для матрицы размера $(n, m)$.
:::
:::spoiler Разбор
:::info
В этой задаче используется теорема Шпрага-Гранди. Пусть $g[i][j]$ - число Гранди для матрицы размера $(n, m)$. Тогда, если в матрице один ряд/столбец и всего не более $S$ клеток, то $g[i][j]$ = 0, и позиция проигрышная. Иначе, $g[i][j]$ равно MEX среди всех значений ($g[k][j]$ ^ $g[i - k][j]$) ($1 \le k < i$) и ($g[i][k]$ ^ $g[i][j - k]$) ($1 \le k < j$).

Асимптотика - $O(N \cdot M \cdot (N + M))$.
:::

# [G3. Смак](https://codeforces.com/gym/501344/problem/G3)
:::spoiler Подсказка 1
:::info
Воспользуемся функцией Гранди.
:::
:::spoiler Подсказка 2
:::info
Заметим закономерность в функции Гранди.
:::
:::spoiler Разбор
:::info
Пусть $g_i$ - функция Гранди для числа $i$. Тогда $g_i$ равен MEX из $g_{i-1}$ и $g_{\varphi(i)}$.

Посмотрим на значения $g_i$. Первые 20 значений: 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0. Несложно заметить, что после первых четырёх чисел мы видим период $(1, 0)$. Значит, при $n > 4$ Ургант побеждает при чётном $n$, а при нечётном - Сафонов, при этом Ургант побеждает с помощью первой операции. Случаи с $n \le 4$ проверим вручную.

Асимптотика: $O(1)$.
:::

# [G4. Деление кучки](https://codeforces.com/gym/501344/problem/G4)
:::spoiler Подсказка 1
:::info
Воспользуемся функцией Гранди.
:::
:::spoiler Подсказка 2
:::info
Будем рекурсивно решать задачу для числа $n$.
:::
:::spoiler Подсказка 3
:::info
Выражение $a$ ^ $a$ ^ $a$ ^ $a$ ... ^ $a$ равно 0 или $a$ в зависимости от чётности количества чисел в нём.
:::
:::spoiler Разбор
:::info
Пусть $g_x$ - функция Гранди для числа $x$. Тогда $g_x$ равен MEX из $g_{x / a_i}$ ^ $g_{x / a_i}$ ^ $g_{x / a_i}$ ^ ... (всего в выражении $a_i$ чисел; $x$ должно нацело делиться на $a_i$). Заметим, что если $a_i$ чётное, то выражение равно 0, а иначе оно равно $g_{x / a_i}$. Значит, для числа $n$ достаточно знать значение $x / a_i$.

Будем решать задачу рекурсивно, найдя для текущего $x$ значение $g_x$. Рекурсия считает функцию Гранди только для делителей $n$ (их не более $\sqrt[3]{n}$), проверяя каждое из чисел в массиве $a$.

Асимптотика: $O(\sqrt[3]{n} \cdot m)$.
:::

# [G5. Раскраска графа](https://codeforces.com/gym/501344/problem/G5)
:::spoiler Подсказка 1
:::info
Пусть $g[i][x1][x2]$ - функция Гранди для цепочки из $i$ вершин, где $x1$ и $x2$ - значения слева и справа от цепочки.
:::
:::spoiler Подсказка 2
:::info
Заметим закономерность в функции Гранди.
:::
:::spoiler Разбор
:::info
Пусть $g[i][x1][x2]$ - функция Гранди для цепочки из $i$ вершин, где $x1$ и $x2$ - значения слева и справа от цепочки. Тогда, $g[i][x1][x2]$ равно MEX среди всех значений $g[pos - 1][x1][cur]$ ^ $g[i - pos][cur][x2]$, где $pos$ - позиция вершины, которую мы красим, а $cur$ - цвет покрашенной вершины.

Посмотрим, как выглядит функция Гранди.

$\textbf{Числа Гранди в виде матрицы 3х3:}$

Длина цепочки равна 1:
1 1 1
1 1 0
1 0 1
Длина цепочки равна 2:
0 2 2
2 1 0
2 0 1
Длина цепочки равна 3:
1 3 3
3 1 0
3 0 1
Длина цепочки равна 4:
0 4 4
4 1 0
4 0 1
Длина цепочки равна 5:
1 5 5
5 1 0
5 0 1
$\textbf{Длина цепочки равна sz:}$
$sz$%$2$ $sz$ $sz$
$sz$ $sz$%$2$ $0$
$sz$ $0$ $sz$%$2$

Тогда во введённой строке найдём все цепочки из вершин и цвета их соседей, и обновим итоговую функцию Гранди.

Асимптотика: $O(N)$.
:::

# [G6. poppin' bottles in the ice, like a blizzard](https://codeforces.com/gym/501344/problem/G6)

:::spoiler Подсказка 1
:::info
Пусть $g_i$ - функция Гранди для вершины $i$. К сожалению, $g_i$ не равно MEX всех её детей, так как мы не учитываем ребро от текущей вершины до ребёнка.
:::

:::spoiler Подсказка 2
:::info
Дерево со значением $g_i=x$ эквивалентно бамбуку с $x$ рёбрами.
:::

:::spoiler Поиск ответа
:::info
Пусть $g_i$ - функция Гранди для вершины $i$. К сожалению, $g_i$ не равно MEX всех функций Гранди её детей, так как мы не учитываем ребро от текущей вершины до ребёнка. Заметим, что дерево со значением $g_i=x$ эквивалентно бамбуку с $x$ рёбрами. Тогда, добавляя одно ребро к началу нашего потомка, мы по сути добавим одно ребро к бамбуку (добавим один камень к кучке в ниме). Значит, $g_i$ равно MEX среди всех значений $g_{to}+1$, где $to$ - потомок вершины $i$.

Асимптотика: $O(n)$.

Разбор этой задачи без восстановления вершины: https://youtu.be/qkKunQ-ifPA?t=11941
:::

:::spoiler Восстановление вершины
:::info
Итак, нам нужно найти вершину, удалив поддерево которй мы получим значение $g_r=0$. Будем решать задачу рекурсивно. Изначально мы находимся в вершине $r$ и хотим, что в ней было число 0. Пусть мы решаем задачу для вершины $v$ и хотим, чтобы в ней было число $x$. Тогда, давайте рекурсивно спустимся во всех её детей ($to$ - текущий ребёнок), передав некоторое значение $val$. Чтобы найти это значение, сначала удалим из $dp_v$ старое значение $dp_{to}+1$ ($dp_v$ станет равным $dp_v$ ^ $(dp_{to}+1)$). Мы же хотим, чтобы итоговое значение в вершине $v$ было равно $x$, поэтому новое значение $dp_{to}+1$ будет равно $dp_v$ ^ $(dp_{to}+1)$ ^ $x$. Значит, $val$ = $dp_v$ ^ $(dp_{to}+1)$ ^ $x$ - 1. Если для вершины $v$ значение $val = -1$, то этой вершины в дереве быть не должно. Тогда уладим эту вершину, обрубив ребро этой вершины с её предком.

Асимптотика: $O(n)$.
:::
# [G7. Дельта альфа альфа штрих](https://codeforces.com/gym/501344/problem/G7)
:::spoiler Разбор
:::info
Пусть $g_i$ - функция Гранди для вершины $i$. Тогда, при подсчёте всех значений мы получим асимптотику $O(2^n)$. Это много. Для оптимизации воспользуемся Альфа-Бета отсечением.

Разбор этой задачи с объяснением Альфа-Бета отсечения: https://youtu.be/qkKunQ-ifPA?t=14239
:::

# [N1. Включаем, исключаем, фиксируем прибыль](https://codeforces.com/gym/501344/problem/N1)
:::spoiler Подсказка
:::info
Зачем при подсчёте ответа рассматривать все числа от 2 до $K$?
:::
:::spoiler Разбор
:::info
Заметим, что при проверке числа на то, что оно не делится на числа на отрезке от 2 до $K$, достаточно проверять только простые числа. Таких чисел на отрезке от 2 до 30 всего 10: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.

Осталось решить задачу только для простых чисел от 2 до $K$. Воспользуемся методом включений-исключений. Пусть во множестве простых чисел мы взяли какое-то подмножество размера $sz$ с произведением $pr$. Тогда нужно прибавить к ответу $(-1)^{sz} \cdot pr$.

Асимптотика: $O(2^{Kprimes} \cdot Kprimes)$ для одного тестового запроса, где $Kprimes$ - кол-во простых от 2 до $K$.
:::

# [N2. Разноцветные маркеры](https://codeforces.com/gym/501344/problem/N2)
:::spoiler Подсказка 1
:::info
$a + b$ - количество клеток в большом прямоугольнике. Переберём меньшую сторону этого прямоугольника среди делителей $a + b$.
:::
:::spoiler Подсказка 2
:::info
Пусть меньшая сторона большого прямоугольника равна $w$ и красные клетки будут образовывать прямоугольник в левом верхнем углу. Как проверить, что такой прямоугольник существует?
:::
:::spoiler Разбор
:::info
$a + b$ - количество клеток в большом прямоугольнике. Переберём меньшую сторону этого прямоугольника среди делителей $a + b$.

Пусть меньшая сторона большого прямоугольника равна $w$ и красные клетки будут образовывать прямоугольник в левом верхнем углу. Тогда стороны этого прямоугольника будут делителями $a$. При этом, сторона, параллельная меньшей стороне большого прямоугольника, будет не более $w$. Чем больше одна сторона красного прямоугольника, тем меньше другая (т.к. его площадь фиксирована). Тогда, найдём в списке делителей наибольший (пусть он равен $del$), меньший, чем $w$, с помощью бинарного поиска и проверим, вмещается ли вторая сторона красного прямоугольника в большой прямоугольник ($\frac{a}{del} \le \frac{a+b}{w}$). Если да, обновим ответ для задачи. Аналогичную проверку делаем и с синим прямоугольником.

Асимптотика: $O(\sqrt[3]{a + b} \cdot (log(\sqrt[3]{a}) + log(\sqrt[3]{b})))$.

Оригинальный разбор: https://codeforces.com/blog/entry/61439
:::

# [N3. Футбольный сезон](https://codeforces.com/gym/501344/problem/N3)
:::spoiler Подсказка
:::info
$d$ побед дают такое же количество очков, как и $w$ ничьих.
:::
:::spoiler Разбор
:::info
$d$ побед дают такое же количество очков, как и $w$ ничьих. Так как проигрыши дают 0 очков и их можно использовать сколько угодно раз, то нам выгодно набирать как можно больше очков за один матч. Значит, $d$ побед выгоднее, чем $w$ ничьих, и тогда можно просто брать $d$ побед, пока нам позволяют это очки и матчи. Проще говоря, возьмём $\frac{n}{d \cdot w}$ раз по $d$ побед.

Теперь осталось добрать оставшиеся очки. Переберём $ost$ - остаток от деления количества побед на $d$. Тогда количество ничей - $\frac{ostpoints - ost * w}{d}$, где $ostpoints$ - оставшиемся очки. Если ответ получился нецелый, то для текущего нет решения. Если частное меньше нуля, можно откатить $d$ побед и добавить $w$ к количеству ничей (если у нас есть хотя бы $d$ побед). В итоге мы получаем количество побед и ничей, и если их сумма не более $n$, добиваем количество матчей до $n$ с помощью проигрышей, а иначе для текущего остатка решения не существует.

Асимптотика: $O(d)$.

Оригинальный разбор: https://codeforces.com/blog/entry/70553
:::

# [N4. Кто не будет решать математику - пойдёт красить забор](https://codeforces.com/gym/501344/problem/N4)
:::spoiler Подсказка 1
:::info
Пусть $a + b$ равно некому $k$. Тогда строка должна иметь период $k$. Если это так, то максимальная позиция единицы во всех блоках (по модулю $k$) должна быть меньше минимальной позиции нуля (по модулю $k$) во всех блоках. Это условие не только достаточное, но и необходимое.
:::
:::spoiler Подсказка 2
:::info
В задаче применяется гармонический ряд.
:::
:::spoiler Разбор
:::info
Пусть $a + b$ равно некому $k$. Тогда строка должна иметь период $k$. Если это так, то максимальная позиция единицы во всех блоках (по модулю $k$) должна быть меньше минимальной позиции нуля во всех блоках (по модулю $k$). Это условие не только достаточное, но и необходимое.

Будем хранить две разреженные таблицы (sparse table). В одной для отрезка $(l, r)$ сохраним самый правый ноль, во второй - самую левую единицу. Найдём максимальную позицию нуля (по модулю $k$) и минимальную позицию нуля (по модулю $k$) во всех блоках. Если между этими двумя позициями есть ещё позиции, заполним их единицами, так как это не влияет на корректность и максимально увеличивает кол-во чёрных досок. В итоге мы получили префикс из нулей и суффикс из единиц.

Итак, теперь мы умеем находить оптимальные $a$ и $b$ для размера блока $k$ за $O(\frac{|s|}{k})$. Давайте сделаем это для всех $k$ от 1 до $|s|$. В итоге, мы сделаем $O(\frac{|s|}{1})$ + $O(\frac{|s|}{2})$ + $O(\frac{|s|}{3})$ + ... + $O(\frac{|s|}{|s|})$ = $O(|s| \cdot log(s))$ операций.

Асимптотика: $O(|s| \cdot log(s))$.
:::

# [N5. Тоня и Бурёнка-179](https://codeforces.com/gym/501344/problem/N5)
:::spoiler Подсказка 1
:::info
Ответ для $k=x$ и $k=gcd(x,n)$ одинаков. Значит, для $k$ стоит рассматривать только делители $n$. Зная это, попробуйте решить задачу за $O(n \cdot \sqrt[3]{n} \cdot log(n))$.
:::
:::spoiler Подсказка 2
:::info
В этой задаче полезно общее утверждение: для любого массива $c$ длины $k$ верно $k ⋅ max(c_1,c_2,…,c_k) \ge c_1+c_2+…+c_n$.
:::
:::spoiler Подсказка 3
:::info
Попробуйте применить вторую подсказку для $k_1$ и $k_2$ делящимся на $k_1$, где $k_1$, $k_2$ - делители $n$.
:::
:::spoiler Разбор
:::info
Ответ для $k=x$ и $k=gcd(x,n)$ одинаков. Значит, для $k$ стоит рассматривать только делители $n$. Сохраним список делителей $n$ в массив $del$. Пусть $sum[pos][i]$ - полезность для стартовой пары $(pos, del_i)$. Заметим при этом, что можно рассматривать только $pos \le del_i$. При обновлении числа будем проходиться по делителям $n$ и обновлять необходимые значение. Чтобы поддерживать максимальное значение в массиве $sum$, сохраним все его значения в $multiset$. В итоге, мы получаем решение за $O(n \cdot \sqrt[3]{n} \cdot log(n))$.

В этой задаче полезно общее утверждение: для любого массива $c$ длины $k$ верно $k ⋅ max(c_1,c_2,…,c_k) \ge c_1+c_2+…+c_n$. Если применить это для $k_1$ и $k_2$ делящимся на $k_1$, где $k_1$, $k_2$ - делители $n$, то мы поймём, что делитель $k_2$ никак не влияет на ответ. Значит, мы можем не учитывать делители $n$, которые делятся на другой делитель $n$ (не равный $n$). Такие делители представляются в виде формулы $\frac{n}{p}$, где $p$ - простой делитель $n$. Для $n \le 2 \cdot 10^5$ различных простых делителей не более 6.

Сложность этого решения - $O(n \cdot log(n) \cdot 6)$, где 6 это максимальное количество различных простых делителей числа $n$.

Оригинальный разбор: https://codeforces.com/blog/entry/106049
:::

# [mem. Восстановление BST](https://codeforces.com/gym/501344/problem/mem)
:::spoiler Подсказка 1
:::info
Попробуйте придумать $dp[l][r]$ (возможны доп. измерения).
:::
:::spoiler Подсказка 2
:::info
Пусть $dp[l][r][root]$ равно 0 или 1 в зависимости от того, можно ли сделать BST для чисел на отрезке $(l, r)$ и корнем в позиции $root$. Обновляется она за линейное время, и мы получаем решение за $O(n^4)$.
:::
:::spoiler Подсказка 3
:::info
Пусть $edge[l][r][side]$ равно 0 или 1 в зависимости от того, можно ли сделать BST для чисел на отрезке $(l, r)$ и корнем в позиции $l$ или $r$ в зависимости от $side$ ($side$ = {0, 1}). Обновляется она также за линейное время.
:::
:::spoiler Подсказка 4
:::info
$dp[i][j][root] = (edge[i][root][1]$ & $edge[root][j][0])$. Значит, теперь обновление $dp$ работает за $O(1)$.
:::
:::spoiler Разбор
:::info
Пусть $dp[l][r][root]$ равно 0 или 1 в зависимости от того, можно ли сделать BST для чисел на отрезке $(l, r)$ и корнем в позиции $root$. Обновляется она за линейное время (слева и справа должны быть вершины $lft$ и $rght$, для которых $dp[l][root - 1][lft]$ и $dp[root + 1][r][rght]$ равны 1, и при этом значения в $lft$ и $rght$ и значение в $root$ не взаимно просты), и мы получаем решение за $O(n^4)$.

Оптимизируем это решение. Пусть $edge[l][r][side]$ равно 0 или 1 в зависимости от того, можно ли сделать BST для чисел на отрезке $(l, r)$ и корнем в позиции $l$ или $r$ в зависимости от $side$ ($side$ = {0, 1}). Обновляется она также за линейное время (так же, как и в $dp$).

Заметим, что значение $dp[i][j][root]$ задаётся как $(edge[i][root][1]$ & $edge[root][j][0])$. Значит, теперь обновление $dp$ работает за $O(1)$. Итого, мы можем считать оба массива за $O(n^3)$.

Асимптотика: $O(n^3)$.

Оригинальный разбор: https://codeforces.com/blog/entry/61323
:::