Сборник Олпрогера

Разделяй и властвуй

Бывает такое, что решение, работающее за квадратичное время тяжело оптимизировать, но тут на помощь приходит метод разделяй и властвуй (divide and conquer) , или разделяйка, которая позволяет в большинстве случаев сократить время работы алгоритма до O(n log n). Увидеть идею оптимизации разделяй и властвуй бывает действительно трудно, поэтому я подготовил несколько задач для практики.

Ознакомиться с идеей можно тут, здесь и там.

Задачки для практики :

Ceil и гондолы - учебная задача на применение оптимизации ДП с помощью разделяйки.
Перестроение лемуров - еще одна задача на применение оптимизации ДП.
Прибавления на отрезках - у этой задачи два решения, одно из которых детерминированное и использует разделяйку.
Min + Sum - задача, которая может быть решена с помощью метода разделяй и властвуй, а конкретно, этой идеей.
Сумма - просто идейная задача на разделяйку.
Новогодние покупки - задача на применение идеи, похожей на Dynamic Connectivity problem.
Интересные отрезки - еще одна задача на разделяйку.
Уникальные вхождения - задача на дерево и разделяйку.
Virus - условие только на английском.

Теги:
#разделяй_и_властвуй #оптимизации #daq #divideandconquer #задачи #регион #всерос #cf

👍21

www.tgoop.com/sbornik_olprog/27

1.47K viewsАнтон Никифоров, Jan 18, 2023 at 14:35

Разделяй и властвуй

Бывает такое, что решение, работающее за квадратичное время тяжело оптимизировать, но тут на помощь приходит метод разделяй и властвуй (divide and conquer) , или разделяйка, которая позволяет в большинстве случаев сократить время работы алгоритма до O(n log n). Увидеть идею оптимизации разделяй и властвуй бывает действительно трудно, поэтому я подготовил несколько задач для практики.

Ознакомиться с идеей можно тут, здесь и там.

Задачки для практики :

Ceil и гондолы - учебная задача на применение оптимизации ДП с помощью разделяйки.
Перестроение лемуров - еще одна задача на применение оптимизации ДП.
Прибавления на отрезках - у этой задачи два решения, одно из которых детерминированное и использует разделяйку.
Min + Sum - задача, которая может быть решена с помощью метода разделяй и властвуй, а конкретно, этой идеей.
Сумма - просто идейная задача на разделяйку.
Новогодние покупки - задача на применение идеи, похожей на Dynamic Connectivity problem.
Интересные отрезки - еще одна задача на разделяйку.
Уникальные вхождения - задача на дерево и разделяйку.
Virus - условие только на английском.

Теги:
#разделяй_и_властвуй #оптимизации #daq #divideandconquer #задачи #регион #всерос #cf

BY Сборник Олпрогера