Задача A

Заметим, что количество букв $$$\text{n}$$$ явно задает количество строк $$$\text{one}$$$ в исходной строке, а количество букв $$$\text{z}$$$ явно задает количество строк $$$\text{zero}$$$. Поэтому для решения достаточно было посчитать количество соответствующих букв.

Задача B

Заметим, что $$$x^2 = \frac{(xy) \cdot (xz)}{yz}$$$, если $$$y \neq 0, z \neq 0$$$. Так как чисел в таблице хотя бы 3, и все числа больше нуля, можно таким образом однозначно восстановить квадраты всех чисел, а так как $$$1 \leq a_i$$$, $$$a_i = \sqrt{a_i^2}$$$.

Задача C

Ключевая идея этой задачи состоит в том, что Миша никогда не ходит. Зафиксируем $$$k$$$ и рассмотрим два случая:

1) $$$s[k] \ge s[i]$$$ для всех $$$i < k$$$, в этом случае $$$s[k, k] \le s[l, r]$$$ для любых $$$l \le k$$$ и $$$r \ge k$$$, а значит Аня не может сделать первый ход (выиграл Миша).

2) Существует $$$i < k$$$ такой, что $$$s[i] < s[k]$$$. В этом случае Аня может сделать ход, взяв подстроку $$$s[i, r]$$$. Заметим, что выбрав наименьшее $$$i < k$$$ так, что $$$s[i]$$$ минимально, мы лишаем Мишу возможности сделать свой ход (выиграла Аня).

Итоговое решение: для каждого $$$k$$$ проверить, является ли $$$s[k]$$$ — минимумом на отрезке $$$s[0, k]$$$. Это можно сделать одним проходом проходом по строке слева направо, поддерживая минимум на префиксе. Сложность $$$O(|s|)$$$

Задача D

Сначала рассмотрим случай, когда множество $$$B$$$ состоит только из нечетных чисел. Заметим, что в таком случае если вершины $$$i$$$ и $$$j$$$ соединены ребром, то они имеют различную четность, значит граф уже является двудольным (левая доля -- четные вершины, правая -- нечетные).

Далее заметим, что если в множестве $$$B$$$ рассмотреть числа $$$a$$$ и $$$b$$$, то обязательно существует цикл длины $$$\frac{lcm(a, b)}{a} + \frac{lcm(a, b)}{b}$$$, что тоже самое как $$$\frac{b}{gcd(a, b)} + \frac{a}{gcd(a, b)}$$$. Такой цикл будет нечетной длины тогда и только тогда, когда множитель 2 входит в разных степенях в разложении на простые множители чисел $$$a$$$ и $$$b$$$. Значит, множество $$$B$$$ как минимум должно состоять из чисел с одинаковой степени 2 в разложении на простые множители. Заметим, что если мы поделим элементы такого множества на $$$2^{i}$$$, где $$$i$$$ — максимально возможное, то ничего не изменится, но все числа будут нечетны. А по доказанной лемме в начале — граф, построенный на таком множестве, будет двудольным.

Тогда мы свели нашу задачу к выбору максимального по размеру подмножества множества $$$B$$$, в котором все степени 2 в разложении на простые множители одинаковы. Очевидно, что такая задача решается за $$$O(N \cdot log_2{MAXB_{i}})$$$.

Задача E

Давайте заметим, что если мы посетили вершину $$$u$$$, расположенную на цикле, то тогда мы можем добавить к ответу все числа, расположенные на этом цикле, а так же все числа на пути между $$$u$$$ и $$$s$$$. Это так, потому что мы можем просто пройтись по циклу, вернуться в $$$u$$$, а затем вернуться в $$$s$$$. Но если из данной вершины мы не можем попасть на цикл, значит, мы не можем вернуться обратно. Тогда нам осталось выбрать лучшее ответвление, ведущее к листьям. Начиная с этого момента, существует несколько решений. Давайте обсудим одно из них.

Пускай $$$e_u$$$ ~--- максимальная сумма которую мы можем набрать, если мы находимся в $$$u$$$ и хотим идти только в ответвления. Первым делом, давайте добавим все листья, кроме $$$s$$$ вершины в очередь или стэк. Затем давайте брать очередную вершину $$$u$$$ и смотреть на её предка $$$p$$$. Давайте уменьшим степень вершины $$$v$$$ и обновим $$$e_v = \max(e_v, e_u + w_u)$$$. Если степень $$$v$$$ стала равна единице, значит $$$v$$$ стала листом, поэтому давайте добавим её в очередь, если она не $$$s$$$. Получается, что на каждом шаге мы удаляем из графа один из листьев и пересчитываем $$$e$$$ для его предка.

В конце концов, мы рассмотрели все вершины, которые не принадлежат циклу и не принадлежат пути из $$$s$$$ до одного из циклов. Нам осталось просуммировать максимальное $$$e_u$$$, где $$$u$$$ — рассмотренная вершина, с суммой всех не рассмотренных вершин.

Также существуют решения разбивающие граф на компоненты рёберной двусвязности и считающие динамику на дереве.

Задача F

Заметим, что элемент $$$a$$$ предок элемента $$$b$$$, если он минимум на отрезке между $$$a$$$ и $$$b$$$. Посчитаем для изначальной перестановки кол-во предков для элемента. Когда мы убираем элемент $$$l$$$ слева, у всех элементов между ним и самым левым меньше него становится на одного предка меньше. Аналогично, когда мы добавим его справа, у всех элементов между ним и самым правым меньше него станет на одного предка больше, а кол-во предков у самого элемента $$$l$$$, добавленного справа, на один больше, чем кол-во предков у самого правого элемента меньше него. Кол-во предков можно хранить в дереве отрезков на максимум с прибавлением на отрезке, если приписать к последовательности ее саму же.

Задача G

Разбор пока не готов.