Дорогие участники сборов, приветствуем вас!

Ранее вам на почту пришли ваш логин и пароль от системы. По ним вы можете принять участие во всех контестах.

Тренировки пройдут по этой ссылке: https://algocourses.ru/sbornik-jan24/

Рекомендуем вам подписаться на канал с новостями сборов. Так вы сможете оперативно узнавать о всех событиях наших тренировок!
Ссылка: https://t.me/sbory2024
Также приглашаем вас в чат, в котором вы сможете обсудить задачи после соревнования и задать вопросы преподавателям.
Ссылка: https://t.me/sbory2024_chat

Желаем вам успехов!

Тинькофф Образование открывает набор на бесплатный курс подготовки к олимпиадам по программированию для школьников 5—11 классов 🧠
Среди наших учеников — десятки победителей и призеров Всероссийской олимпиады.

Встречаемся один раз в неделю в течение учебного года. Занятия проходят в офисах Тинькофф в Москве, Екатеринбурге, Санкт-Петербурге, Новосибирске, Ижевске, Челябинске, Казани, Томске и Минске, а также транслируются онлайн для школьников из других городов. На курсе будут четыре параллели разной сложности, поэтому вы будете обучаться с ребятами своего уровня подготовки.

Подать заявку и сдать вступительный экзамен можно до 16 января включительно

Теги: #партнерскийпост

Сегодня запостим пушку!
Ждите…

До региона осталась ровно одна неделя, давайте обсудим самые необходимые вещи, которые нужно сделать/повторить/изучить перед регионом👇👇👇

Сегодня у Сборника день рождения! Нам ровно год. За год мы сделали большой прорыв и смогли реализовать все задуманное!

Спасибо, что стали частью нашего сообщества и остаетесь с нами💙

Неофициальный разбор длинного тура открытой олимпиады школьников по программированию

https://codeforces.com/blog/entry/124717

Автор: @tiom4eg

Друзья, уже завтра состоится первый тур регионального этапа ВСОШ по информатике!

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

У каждого из вас своя стратегия на тур, однако, мы назовем 3 важных аспекта:
- Набирайте баллы
- Не засиживайтесь на одной задаче
- Не переживайте, не думайте о результатах других и не думайте, что будет после.
Делайте то, что вы умеете!

Помните одну важную вещь: если вы будете переживать или психовать, то ваш результат будет ухудшаться с каждой минутой тура. Важно сосредоточиться и решать задачи!

Больше никаких советов, только вперед!

Помните, что вы все победители. Вы поставили себе цели и вы к ним идете. Вас никто не заставляет это делать, но вы это делаете. Это достойно уважения. Я верю, что каждый из вас достигнет поставленных целей!

От имени Сборника желаю вам успехов на регионе!

Неофициальный разбор первого тура регионального этапа

A — https://code-bank.ru/tasks/e3501aab51a9de52af5b7ae6fa87323de342b31b

B — https://code-bank.ru/tasks/22eac40fa17f2226fd684c741cf345bfc77f778d

C — https://code-bank.ru/tasks/3d781c47d5204bcf7eca55a4b6b7ff47498fb706

D — https://code-bank.ru/tasks/73c118094a4e34bb776ef2a6751fb776b9872e0c

Бот для сообщений команде: @codebank_service_bot (/message)

Подготовили: https://t.me/codebank_community при поддержке https://t.me/sbornik_olprog

*Мы открыты для предложений и замечаний, ждем вашего фидбека

p.s. решения бесплатные, надо зарегистрироваться

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

А:
Давайте попробуем исходную рассадку сделать симметричной. В целом понятно, что любая расстановка должна содержать эту рассадку, как подмножество. Дальше уже можно просто добавлять пассажиров парами в две свободные симметричные клетки.
Б:
Назовем элемент B_i центральным, где знаки меняются. Понятно, что в битонической последовательности центральный элемент ровно один. Поэтому давайте переберем какой элемент будет центральным и найдем самый дальний возможный левый конец и аналогично самый дальний возможный правый конец (это можно сделать многими способами - это стандартная задача). назовем их L и R. Достаточно понятно, что начало битонической последовательности, где ее центральный элемент на позиции i может начаться на позиции L и вплоть до i. Аналогично с R. Очевидно, что количество таких последовательностей является произведением количества валидных левых и правых концов. Задача решается из соображений, что нам удобно перебрать и как склеить два независимых конца.
C:
Заметим, что на самом деле порядок удаления строк и столбцов нам не важен. Мы можем заранее выбрать какие удалим строки и какие строки и найти сумму получившейся подматрицы. Давайте рассмотрим 2 ^ h вариантов, какие мы удалим строки. Теперь в получившейся матрице нужно выбрать такое подмножество столбцов, что их сумма = s. Это стандартная задача на рюкзак, которую можно решать разными способами. В данном случае нам будет удобен способ, использующий метод Meet in the middle, который найдет такой способ за 2 ^ (w / 2). Итого мы получаем решение за 2 ^ h * 2 ^ (w / 2), что должно получать полный балл.
Задача требует два наблюдения: порядок на самом деле не важен и умение решать задачу о рюкзаке таким способом.
Д:
Первая же идея в задаче - это бинпоиск по ответу. Давайте рассмотрим самую дальнюю вершину от корня, если ее расстояние <= h (что мы перебираем в бинпоиске), то мы добились нужного. Иначе мы должны какого - то ее предка прикрепить к корню. В целом понятно, что самый лучший из таких - это на предок на расстоянии h - 1 от вершины (найти это вершину можно, как h - 1 вершину на пути от v до root, где root - текущий корень, что можно искать с помощью бинарных подъемов). Мы можем мысленно поддерево это вершины удалить, так как все ее потомки также имеют расстояние <= h. Продолжим процесс, пока число возможных ребер, которые можно добавить не кончится. Как это аккуратно поддерживать? Воспользуемся популярной идей. Давайте запишем обход дерева в массив, подвесив ее за вершину 0. tin[v] - время входа в вершину, а tout[v] - время выхода. Тогда все вершины поддерева имеют индекс в массиве id >= tin[v] && id <= tout[v] (то есть все лежат на некотором отрезке в массиве обхода). Тогда для root = 0, уменьшить расстояние в поддереве можно с помощью прибавления на отрезке на построенном дереве отрезке, а искать самую дальнюю вершину с помощью max на всем массиве. Как не перестраивать это дерево отрезков для различных корней? Тут удобно будет заметить, что на самом деле нужно прибавить число на всем массиве и вычесть в поддереве, в котором лежит новый корень в исходно подвешенном поддереве (рекомендую самому подумать, почему такой метод действительно работает). Это поддерево легко можно найти с помощью бинпоиска. Склеивая все эти идеи, мы получаем решение, которое работает за N * K * log^2(N). Это уже может зайти, если это аккуратно написать. Заметим интересную идею, ответ для вершины соседней по ребру в дереве отличается не более чем на 1. Давайте искать ответ для вершин в порядке обхода дфс к примеру и проверять только ans, ans - 1, ans + 1. Таким образом, мы избавились от большого количества бинпоисков (достаточно запустить его только одной вершины). И получаем решение за NK * log(N). Задача требует небольшого анализа над тем, как устроен ответ и умение использовать структуры данных для деревьев.

Автор: Александр Сушин

Рекомендации на сегодня

Первый тур прошел, у вас уже есть определенные результаты. Рекомендуем проанализировать ваши ошибки, а также то, что вы сделали правильно.

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

А сейчас забиваем на все, что было вчера и разгружаем голову. Можете позаниматься любимыми делами или погулять с друзьями. Можете попробовать сделать что-нибудь необычное(например день не заходить в соц. сети, это поможет не думать о завтра). Главное после анализа — не думать о туре до завтра. А уже завтра собраться и делать свое дело!

Хорошего дня, желаем вам завтра удачи!

Желаем удачи!

и халявок…)

Официальный разбор задач регионального этапа:
https://neerc.ifmo.ru/school/archive/2023-2024/ru-olymp-regional-2024-solutions.pdf

Приглашаем поучаствовать!