CF 942D. Решение.
Условие задачи.
1. Первая идея довольно стандартная, но все равно красивая. Пусть для любой пары чисел
2. Как проверять, можно ли получить
3. Если вспомнить, что ребро
4. Как просто выбрать
Доказательство того, что этот код делает ровно то, что нужно, оставлю в качестве упражнения для любознательных читателей.
Условие задачи.
1. Первая идея довольно стандартная, но все равно красивая. Пусть для любой пары чисел
(x, y) мы умеем за быстро определять, можно ли x превратить в y. Найдем в тупую минимальное число, в которое можно превратить a[0] и превратим. Потом сделаем тоже самое для a[1], но начиная проверять только с a[0]. Хоть для каждого конкретного числа мы можем проверить O(n) вариантов, суммарно мы проверим не O(n^2) вариантов, а только O(n).2. Как проверять, можно ли получить
y из x? Сделаем граф, в котором проведем ребро из i в next[i]. Такой граф состоит из циклов и деревьев, которые к ним подвешены. Давайте для каждого цикла веберем какую-то вершину root, удалим ребро root -> next[root], получим дерево с корнем в root. В таком графе проверка "можно ли x превратить в y" это тоже самое, что вершина x лежит в поддереве y. А это стандартная задача, нужно обойти дерево с помощью dfs, для каждой вершины i запомнить время входа tin[i] и выхода tout[i] из нее. Тогда условие x в поддреве y эквивалентно tin[y] <= tin[x] <= tout[y].3. Если вспомнить, что ребро
root -> next[root] все-таки существует, то чтобы определить достижимость y из x нужно рассмотреть два варианта. Либо x лежит в поддереве y, либо next[root] лежит в поддереве y.4. Как просто выбрать
root для каждого цикла? Можно сделать это в три строки кода с помощью DSU (функция union(x, y) добавляет ребро x-y и возвращает true, если x и y находились в разных компонентах связности).for i in 0..n {
if !dsu.union(i, next[i]) {
// mark `i` as root
}
}Доказательство того, что этот код делает ровно то, что нужно, оставлю в качестве упражнения для любознательных читателей.