Telegram Group & Telegram Channel
CF 942D. Решение.

Условие задачи.

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
}
}


Доказательство того, что этот код делает ровно то, что нужно, оставлю в качестве упражнения для любознательных читателей.



group-telegram.com/bminaiev_blog/67
Create:
Last Update:

CF 942D. Решение.

Условие задачи.

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
}
}


Доказательство того, что этот код делает ровно то, что нужно, оставлю в качестве упражнения для любознательных читателей.

BY Боря программирует

❌Photos not found?❌Click here to update cache.


Warning: Undefined variable $i in /var/www/group-telegram/post.php on line 260

Share with your friend now:
group-telegram.com/bminaiev_blog/67

View MORE
Open in Telegram


Telegram | DID YOU KNOW?

Date: |

"We're seeing really dramatic moves, and it's all really tied to Ukraine right now, and in a secondary way, in terms of interest rates," Octavio Marenzi, CEO of Opimas, told Yahoo Finance Live on Thursday. "This war in Ukraine is going to give the Fed the ammunition, the cover that it needs, to not raise interest rates too quickly. And I think Jay Powell is a very tepid sort of inflation fighter and he's not going to do as much as he needs to do to get that under control. And this seems like an excuse to kick the can further down the road still and not do too much too soon." The account, "War on Fakes," was created on February 24, the same day Russian President Vladimir Putin announced a "special military operation" and troops began invading Ukraine. The page is rife with disinformation, according to The Atlantic Council's Digital Forensic Research Lab, which studies digital extremism and published a report examining the channel. Ukrainian forces successfully attacked Russian vehicles in the capital city of Kyiv thanks to a public tip made through the encrypted messaging app Telegram, Ukraine's top law-enforcement agency said on Tuesday. Following this, Sebi, in an order passed in January 2022, established that the administrators of a Telegram channel having a large subscriber base enticed the subscribers to act upon recommendations that were circulated by those administrators on the channel, leading to significant price and volume impact in various scrips. Stocks closed in the red Friday as investors weighed upbeat remarks from Russian President Vladimir Putin about diplomatic discussions with Ukraine against a weaker-than-expected print on U.S. consumer sentiment.
from jp


Telegram Боря программирует
FROM American