Центроидная декомпозиция
Центроидная декомпозиция, или просто центроиды, довольно интересный и часто встречающийся алгоритм. В последнее время во многих олимпиадах начали встречаться центроиды. К примеру: Открытая олимпиада школьников, ЗЭ ВсОШ, МОШ. Сам по себе алгоритм несложный и после практики в несколько задач его можно будет писать на реальных турах. Сегодня я подготовил несколько таковых задача на центроиды для практики.
Ознакомиться с центроидной декомпозицией можно тут или тут
Мой сборник задач:
Командир Ciel - задача просто на написание центроидной декомпозиции
Ксюша и Дерево - задача имеет два решения, одно из которых центроидная декомпозиция
Палиндромы в дереве - учебная задача на центроиды и на умение пользоваться map
Подсчёт GCD - учебная задача на центроиды с gcd, но есть и решение без центроидов
Цифровое дерево - стандартная учебная задача на центроиды и теорию чисел
0-1-Дерево - один из пример задач, которая легко решается центроидами, но при этом у неё есть и другие решения
Столицы - задача D регионального этапа, которую можно решить центроидами, но сложно
Новые кампусы! - задача C заочного тура Открытой олимпиады, задача очень тяжелая
Сигнализация! - задача D ЗЭ ВсОШ, тяжелая задача на центроиды
Задача расположены в порядке их наилучшего прорешивания.
Теги: #тренировка #задачи #центроиды #регион #всерос #практика
Центроидная декомпозиция, или просто центроиды, довольно интересный и часто встречающийся алгоритм. В последнее время во многих олимпиадах начали встречаться центроиды. К примеру: Открытая олимпиада школьников, ЗЭ ВсОШ, МОШ. Сам по себе алгоритм несложный и после практики в несколько задач его можно будет писать на реальных турах. Сегодня я подготовил несколько таковых задача на центроиды для практики.
Ознакомиться с центроидной декомпозицией можно тут или тут
Мой сборник задач:
Командир Ciel - задача просто на написание центроидной декомпозиции
Ксюша и Дерево - задача имеет два решения, одно из которых центроидная декомпозиция
Палиндромы в дереве - учебная задача на центроиды и на умение пользоваться map
Подсчёт GCD - учебная задача на центроиды с gcd, но есть и решение без центроидов
Цифровое дерево - стандартная учебная задача на центроиды и теорию чисел
0-1-Дерево - один из пример задач, которая легко решается центроидами, но при этом у неё есть и другие решения
Столицы - задача D регионального этапа, которую можно решить центроидами, но сложно
Новые кампусы! - задача C заочного тура Открытой олимпиады, задача очень тяжелая
Сигнализация! - задача D ЗЭ ВсОШ, тяжелая задача на центроиды
Задача расположены в порядке их наилучшего прорешивания.
Теги: #тренировка #задачи #центроиды #регион #всерос #практика
Регион близко...
Кто не знал, сущетсвуют дистуры для различных этапов всероса в открытом доступе, на которые можно зарегистрироваться и начать решать в записи прямо сейчас! (+ архив олимпиад)
https://algocode.ru/main/13/
Теги: #тренировка #туры #регион #всерос #регион
Кто не знал, сущетсвуют дистуры для различных этапов всероса в открытом доступе, на которые можно зарегистрироваться и начать решать в записи прямо сейчас! (+ архив олимпиад)
https://algocode.ru/main/13/
Теги: #тренировка #туры #регион #всерос #регион
Convex Hull Trick
Все чаще и чаще во всяких контестах и на олимпиадах встречается такой метод оптимизации, как convex hull trick. В неучебных задачах он далеко не всегда очевиден. В целом метод несложный, а главное идейный. Поняв идею, можно будет его написать, не затрудняясь.
Ознакомиться с методом можно тут, или тут, или даже тут.
Учебные задачи:
Калила и Димна на лесозаготовках - первая учебная задача на CHT
Орехус и прямоугольники - вторая типичная учебная задача CHT
Транспортировка кошек - баян на CHT
Houses and Schools - условие только на английском
Задачи нормального уровня:
Avoiding Airports - условие только на английском
Доставка пиццы - прикольная задача на структуры данных.
Split the Sequence - задача с APIO14, условие только на английском
Долгий путь домой - задача с недавнего div 2 на CHT, пишется несложно
YATP - задача на деревья и CHT. Условие только на английском
Managing Telephone Poles - условие только на английском
Cумма префиксных сумм - задача на деревья и CHT. Задача, чтобы потренировать силу рук
Прогулка по графу - неочевидное применение CHT
Сложные задачи:
Очередная задача на разбиения - задача на силу рук
Иннофоны - задача С ЗЭ ВсОШ, прикольная задача на CHT
Самая удивительная вершина - G global round codeforces, советую решить после задачи Иннофоны,
Теги: #кхт #оптимизации #cht #convexhultrick #задачи #регион #всерос #cf
Автор: Тимофей Ижицкий
Все чаще и чаще во всяких контестах и на олимпиадах встречается такой метод оптимизации, как convex hull trick. В неучебных задачах он далеко не всегда очевиден. В целом метод несложный, а главное идейный. Поняв идею, можно будет его написать, не затрудняясь.
Ознакомиться с методом можно тут, или тут, или даже тут.
Учебные задачи:
Калила и Димна на лесозаготовках - первая учебная задача на CHT
Орехус и прямоугольники - вторая типичная учебная задача CHT
Транспортировка кошек - баян на CHT
Houses and Schools - условие только на английском
Задачи нормального уровня:
Avoiding Airports - условие только на английском
Доставка пиццы - прикольная задача на структуры данных.
Split the Sequence - задача с APIO14, условие только на английском
Долгий путь домой - задача с недавнего div 2 на CHT, пишется несложно
YATP - задача на деревья и CHT. Условие только на английском
Managing Telephone Poles - условие только на английском
Cумма префиксных сумм - задача на деревья и CHT. Задача, чтобы потренировать силу рук
Прогулка по графу - неочевидное применение CHT
Сложные задачи:
Очередная задача на разбиения - задача на силу рук
Иннофоны - задача С ЗЭ ВсОШ, прикольная задача на CHT
Самая удивительная вершина - G global round codeforces, советую решить после задачи Иннофоны,
Теги: #кхт #оптимизации #cht #convexhultrick #задачи #регион #всерос #cf
Автор: Тимофей Ижицкий
Codeforces
Problem - C - Codeforces
Codeforces. Programming competitions and contests, programming community
Отжиг
Бывают задачи, в которых непонятно существует ли алгоритм, точно находящий ответ, либо можно получить баллы за ответ приближенный к точному. В таких задачах часто используются методы локальной оптимизации и неточные алгоритмы, один из которых - метод имитации отжига.
Ознакомиться с методом можно тут и тут.
Пдфка для особо заинтересованных
Контест на отжиг на informatics
Div2 E на отжиг
Хорошие раскраски - задача С второго дня регионального этапа ВсОШ 2021
Теги: #отжиг #оптимизации #методотжига #задачи #регион #всерос #cf
Автор: @olptashim
Бывают задачи, в которых непонятно существует ли алгоритм, точно находящий ответ, либо можно получить баллы за ответ приближенный к точному. В таких задачах часто используются методы локальной оптимизации и неточные алгоритмы, один из которых - метод имитации отжига.
Ознакомиться с методом можно тут и тут.
Пдфка для особо заинтересованных
Контест на отжиг на informatics
Div2 E на отжиг
Хорошие раскраски - задача С второго дня регионального этапа ВсОШ 2021
Теги: #отжиг #оптимизации #методотжига #задачи #регион #всерос #cf
Автор: @olptashim
Хабр
Введение в оптимизацию. Имитация отжига
В этой статье я постараюсь максимально доходчиво рассказать о таком простом, но эффективном методе оптимизации, как имитация отжига (simulated annealing). А чтобы не быть причисленным к далёким от...
Эйлеров обход
Не могу сказать, что эта идея уж очень часто применяется, но с помощью нее можно сводить задачи на деревья к массиву и решать их уже на массиве.
Ссылка на нирк
Ссылка на кф
(Автор в статье в целом рассказывает про метод, не обращайте внимания на поставленные им вопросы)
Теги: #эйлеровобход #идея #регион #всерос #cf
Не могу сказать, что эта идея уж очень часто применяется, но с помощью нее можно сводить задачи на деревья к массиву и решать их уже на массиве.
Ссылка на нирк
Ссылка на кф
(Автор в статье в целом рассказывает про метод, не обращайте внимания на поставленные им вопросы)
Теги: #эйлеровобход #идея #регион #всерос #cf
Codeforces
Про эйлеров обход
TL;DR: можно ли одновременно поддерживать эйлеровым обходом LCA, сумму в поддереве и переподвешивание?
Разделяй и властвуй
Бывает такое, что решение, работающее за квадратичное время тяжело оптимизировать, но тут на помощь приходит метод разделяй и властвуй (divide and conquer) , или разделяйка, которая позволяет в большинстве случаев сократить время работы алгоритма до O(n log n). Увидеть идею оптимизации разделяй и властвуй бывает действительно трудно, поэтому я подготовил несколько задач для практики.
Ознакомиться с идеей можно тут, здесь и там.
Задачки для практики :
Ceil и гондолы - учебная задача на применение оптимизации ДП с помощью разделяйки.
Перестроение лемуров - еще одна задача на применение оптимизации ДП.
Прибавления на отрезках - у этой задачи два решения, одно из которых детерминированное и использует разделяйку.
Min + Sum - задача, которая может быть решена с помощью метода разделяй и властвуй, а конкретно, этой идеей.
Сумма - просто идейная задача на разделяйку.
Новогодние покупки - задача на применение идеи, похожей на Dynamic Connectivity problem.
Интересные отрезки - еще одна задача на разделяйку.
Уникальные вхождения - задача на дерево и разделяйку.
Virus - условие только на английском.
Теги:
#разделяй_и_властвуй #оптимизации #daq #divideandconquer #задачи #регион #всерос #cf
Бывает такое, что решение, работающее за квадратичное время тяжело оптимизировать, но тут на помощь приходит метод разделяй и властвуй (divide and conquer) , или разделяйка, которая позволяет в большинстве случаев сократить время работы алгоритма до O(n log n). Увидеть идею оптимизации разделяй и властвуй бывает действительно трудно, поэтому я подготовил несколько задач для практики.
Ознакомиться с идеей можно тут, здесь и там.
Задачки для практики :
Ceil и гондолы - учебная задача на применение оптимизации ДП с помощью разделяйки.
Перестроение лемуров - еще одна задача на применение оптимизации ДП.
Прибавления на отрезках - у этой задачи два решения, одно из которых детерминированное и использует разделяйку.
Min + Sum - задача, которая может быть решена с помощью метода разделяй и властвуй, а конкретно, этой идеей.
Сумма - просто идейная задача на разделяйку.
Новогодние покупки - задача на применение идеи, похожей на Dynamic Connectivity problem.
Интересные отрезки - еще одна задача на разделяйку.
Уникальные вхождения - задача на дерево и разделяйку.
Virus - условие только на английском.
Теги:
#разделяй_и_властвуй #оптимизации #daq #divideandconquer #задачи #регион #всерос #cf
Архивный пост Кости Амеличева про регион
Комментарий из его блога: "...актуально всяким школьникам, которые переживают сейчас из-за олимпиад по информатике. Так что если вы такой — смело читайте, если знакомые такие — смело делитесь."
Ссылка: https://github.com/KiK0S/articles/blob/main/region-is-coming/region-is-coming.md
Теги: #регион #всош
Автор: @kik0s
Комментарий из его блога: "...актуально всяким школьникам, которые переживают сейчас из-за олимпиад по информатике. Так что если вы такой — смело читайте, если знакомые такие — смело делитесь."
Ссылка: https://github.com/KiK0S/articles/blob/main/region-is-coming/region-is-coming.md
Теги: #регион #всош
Автор: @kik0s
Появились списки на Мартовскую смену в Сириусе
Ссылка на программу: https://sochisirius.ru/obuchenie/nauka/smena1460/6854
Проходные баллы:
7-9 — 528
10 — 544
Теги: #всош #регион #сириус
Ссылка на программу: https://sochisirius.ru/obuchenie/nauka/smena1460/6854
Проходные баллы:
7-9 — 528
10 — 544
Теги: #всош #регион #сириус
Бинарные подъемы
Достаточно популярный метод в задачах на деревья. Обычно его связывают с LCA(и рассказывают, когда говорят о LCA), что справедливо. Однако этот метод применяется и на массиве. Например Sparse Table — это и есть "бинапы на массиве". В целом, прикольная идея, которая помогает делать какие-то переходы, имея возможность достигнуть любой позиции/вершины, так как степенями 2 можно получить любое число.
Статьи по теме:
Статья на Algocode Wiki
Статья на Нирке
Бинапы с линейной памятью
Задачи:
Напишите LCA
Дураки и дороги
Duff в армии
Намешали всего, что можно
Задача D
Неочевидная идея
Теги: #lca #бинарныеподъемы #метод #всош #регион
*Любимый метод автора проекта😁
Достаточно популярный метод в задачах на деревья. Обычно его связывают с LCA(и рассказывают, когда говорят о LCA), что справедливо. Однако этот метод применяется и на массиве. Например Sparse Table — это и есть "бинапы на массиве". В целом, прикольная идея, которая помогает делать какие-то переходы, имея возможность достигнуть любой позиции/вершины, так как степенями 2 можно получить любое число.
Статьи по теме:
Статья на Algocode Wiki
Статья на Нирке
Бинапы с линейной памятью
Задачи:
Напишите LCA
Дураки и дороги
Duff в армии
Намешали всего, что можно
Задача D
Неочевидная идея
Теги: #lca #бинарныеподъемы #метод #всош #регион
*Любимый метод автора проекта
Please open Telegram to view this post
VIEW IN TELEGRAM
peltorator.ru
Двоичные подъемы с линейной памятью
Двоичные подъемы с линейной памятью Часто в задачах на деревья используются двоичные подъемы. Они помогают искать LCA (наименьшего общего предка), какую-то функцию на пути и так далее. Однако они занимают $O(n \log n)$ памяти. В этой главе мы рассмотрим альтернативную…
Олимпиадный сезон кончился, но многие, наверняка, хотели бы подготовиться к олимпиадам в следующему году. Я собрал туры, которые составлялись для школьного кружка, сопоставимые по сложности с региональным этапом ВсОШ. Задачи отсюда не пересекаются с задачами регионального этапа и преимущественно взяты с других российских олимпиад. Вход в группу свободен, поэтому можете спокойно прорешивать туры.
Ссылка на группу: codeforces.com/group/fZRmHdsmuy
Автор: Александр Сушин
Теги: #контест #регион #всош
Ссылка на группу: codeforces.com/group/fZRmHdsmuy
Автор: Александр Сушин
Теги: #контест #регион #всош
Codeforces
Contests - Codeforces
Codeforces. Programming competitions and contests, programming community
rotation_45.pdf
111.5 KB
Поворот плоскости на 45 градусов
Регион позади, у многих впереди всеросс. Кто-то сделал выводы и занимается еще более усердно, чтобы в следующем году показать лучший результат. В этом лонгриде описывается довольно известная, но полезная идея - переход от суммы разностей координат в манхэттенской метрике к максимуму.
Теги: #всош #регион
Автор : Карим Миннибаев(@d3j4vY)
Регион позади, у многих впереди всеросс. Кто-то сделал выводы и занимается еще более усердно, чтобы в следующем году показать лучший результат. В этом лонгриде описывается довольно известная, но полезная идея - переход от суммы разностей координат в манхэттенской метрике к максимуму.
Теги: #всош #регион
Автор : Карим Миннибаев(@d3j4vY)