Регион близко...
Кто не знал, сущетсвуют дистуры для различных этапов всероса в открытом доступе, на которые можно зарегистрироваться и начать решать в записи прямо сейчас! (+ архив олимпиад)
https://algocode.ru/main/13/

Теги: #тренировка #туры #регион #всерос #регион

Задача

Дано n<=50 натуральных различных чисел. a[i]<=1e9.
Требуется найти такое неотрицательное X, что количество полных квадратов среди a[i]+X максимально.
Подсказка: смотрите на разности

Задача взята с codeforces

Теги: #задачадня #codeforces

Интересный метод

Представим жюри загадало дробь p/q, gcd(p, q) = 1, p, q <= 10^9. вам требуется эту дробь угадать, вы можете спросить дробь a/b - соответственно получите {-1, 0, 1} (дробь меньше, равна, больше загаданной) нюанс в том, что вы не можете спросить дробь, у которой a, b > 10^9. существует множество подходов к этой задаче, например запустить спуск по дереву Штерна-Броко (https://ru.m.wikipedia.org/wiki/Дерево_Штерна_—_Броко), или закрепить знаменатель и бинарить числитель. такие методы угадают дробь за Q и QlogQ соответсвенно, где Q граница на p, q. чтобы добиться logQ запросов нужно представить нашу дробь в виде цепной дроби и приближать каждый ее член с помощью бинарного поиска. подробнее про алгоритм написано в комментариях тут: https://codeforces.com/blog/entry/4190?locale=ru именно с помощью этого метода можно сдать Б отбора на СПбГУ

Теги: #дробь #спбгу #деревоштернаброко

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

Ссылка: https://www.tgoop.com/shornik_olprog_chat

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

Автор: Тимофей Ижицкий

Дорогие читатели, рады сообщить, что ОЛПРОГ и Тинькофф Алгоритмы теперь являются партнерами по проекту Сборник Олпрогера.
Спасибо компании Тинькофф за проявленное доверие и по-настоящему большой вклад в развитие проекта!
Мы также благодарим вас, читателей, за проявленный интерес к проекту!

Отжиг

Бывают задачи, в которых непонятно существует ли алгоритм, точно находящий ответ, либо можно получить баллы за ответ приближенный к точному. В таких задачах часто используются методы локальной оптимизации и неточные алгоритмы, один из которых - метод имитации отжига.

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

Пдфка для особо заинтересованных

Контест на отжиг на informatics

Div2 E на отжиг

Хорошие раскраски - задача С второго дня регионального этапа ВсОШ 2021

Теги:  #отжиг #оптимизации #методотжига #задачи #регион #всерос #cf

Автор: @olptashim

Эйлеров обход

Не могу сказать, что эта идея уж очень часто применяется, но с помощью нее можно сводить задачи на деревья к массиву и решать их уже на массиве.

Ссылка на нирк
Ссылка на кф
(Автор в статье в целом рассказывает про метод, не обращайте внимания на поставленные им вопросы)

Теги: #эйлеровобход #идея #регион #всерос #cf

Региональный этап уже очень близко.
Регион выглядит для многих большим барьером, а по факту им не является. Поэтому стоит немного поговорить о нем.
Написано для ребят, кто много работал весь год и в первый раз имеет шансы пройти на всерос
1. Сейчас надо расслабиться. Серьезная подготовка не ведется за три дня.
2. Проходные баллы не высокие. Главное не тильтовать на туре и придерживаться стратегии.
3. Хорошая стратегия: АБС фулл, Д подгруппы.
4. Регион это 2 разных олимпиады: не надо зацикливаться на первом дне.
5. У вас будет день перерыва между турами, сходите погулять с друзьями, чтобы отвлечься.
6. Поспите хорошенько.
7. Проверяейте свои идеи по С и Д. Не надо писать фулл, если заранее понятно, что код будет объемным. Напишите тупняк, который проверяет идею, а потом оптимизируйте его.
8. Не зацикливайтесь на одной задаче, если она долго не идет.
Надо набирать баллы.

Всем удачи!🍀

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

Бывает такое, что решение, работающее за квадратичное время тяжело оптимизировать, но тут на помощь приходит метод разделяй и властвуй (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

Помните reg.prog.cf?
Если нет, то это была классная платформа, куда ребята вводили результаты до их официальной публикации. Так можно было делать предикты баллов прохода на закл, например).
Сейчас сайт переехал сюда: http://reg.algocode.ru

У нас хорошая новость! Опубликованы окончательные результаты длинного отборочного тура.

Решением жюри на очный тур соревнований приглашаются все конкурсные участники, набравшие в длинном отборочном туре не менее 730 баллов.
Конкурсные участники, набравшие не менее 174 и не более 729 баллов, приглашаются к участию в коротком отборочном туре. После окончания короткого тура будет организовано отдельное соревнование, в котором могут принять участие все желающие написать короткой тур вне конкурса.

Так же опубликованы результаты проверки на нарушение правил олимпиады, в том числе несамостоятельное выполнение работы (списывание).

Закончился первый тур региона.

Сегодня не стоит:
- решать какие-то задачи
- переживать из-за результатов первого тура
- ложиться спать поздно

Лучше всего будет прогуляться или как-то по-другому отдохнуть. На личном опыте многих, это помогает написать тур спокойно и достойно.

Всем удачи на втором туре🍀

Разбор регионального этапа

Закончился регион, а тут и Codeforces!

Я и двое редакторов данного замечательного канала хотим пригласить вас на наш Codeforces Round #846 (Div. 2)! Он пройдёт уже завтра в 17:35 по московскому времени.

На раунде вас будут ждать 7 задач! Все задачи подготовлены нами. Его можно порешать ради тренировки, так как он будет полезен как всем начинающим, так и мастерам своего дела!

Подробности можно почитать в анонсе.

Теги: #codeforces #round #раунд #тренировка

Календарь 2022- 2023

Если кто-то не знает, то есть календарик с расписанием олимпиад. Тут достаточно быстро обновляется информация о финалах, так что, помимо наших постов, вы сможете самостоятельно посмотреть расписание в удобном формате.

Автор календаря: Марина Панькова

Переливайка или small-to-large

В задачах на деревья или в задачах, в которых нужно мерджить несколько структур вместе, бывает полезным трюк под названием small-to-large - вместо того, чтобы в случайном порядке объединять объекты, возьмем самый большой объект и перельем все к нему. Тогда каждый объект будет "прилит" не более log N раз (каждый раз, когда он приливается, размер увеличивается хотя бы в 2), и асимптотика будет O(NlogNT(n)), где T(n) - время работы одного "прилива"

Чуть подробнее почитать про small-to-large

Задачи:

Учебная задача - CSES
Понять условие + написать, осторожно с сетами!
Баянчик с IOI, осторожно с вводом/выводом
Сложненькая задачка
Не открывать если хотите писать всерос 2015-2021 годов как тренировку

Теги: #деревья #всерос #легкая_идея