Разбор задач первого отборочного тура ВП(11 класс).
А:
Заметим, что разница между горизонтальными парами всегда равна 1, а между вертикальными всегда m. Для разных k получается разная формула. Не забудем рассмотреть случай k=1 и получаем 100 баллов.
B:
Давайте "выключать" числа от самых маленьких к самым большим по очереди. На каждом этапе с помощью, например дерева отрезков, посчитаем самый длинный отрезок из "выключенных" чисел. Тогда при фиксированном минимальном "включенном" числе, k должно быть больше хотябы на 1, чем посчитанная ранее длинна. Для всех нужных k обновим ответ и получаем свои 100 баллов.
С:
Давайте подвесим дерево и посчитаем для каждой вершины ксор на пути до корня. Тогда ксор пути между вершинами, это ксор посчитанных ксоров(это известный факт).
Нас просят для каждой вершины посчитать до скольких вершин мы сможем дойти так, что ни на каком префиксе ксор на пути не был равен 0.
Это значит, что мы не можем идти дальше, если придем в вершину, до которой ксор на пути равен 0.
То, что ксор на пути между вершинами равен 0 значит, что ксоры на пути от этих вершин до корня равны.
Простое решение с сложной структурой данных:
Давайте сначала соединим все вершины ребрами.
Будем перебирать различные ксоры на путях до корня.
Давайте для фиксированного ксора уберем все из графа все ребра, которые содержат вершины с таким ксором.
Затем для каждой вершины с таким ксором посчитаем сумму размеров компонент, с которыми она была связана изначально и это будет ответ(так как в компонентах не будет вершин с таким ксором, мы сможем дойти до каждой вершины из компоненты).
Потом снова добавим ребра.
Это можно сделать с помощью структуры данных "линк кат три".
Решение без сложной структуры данных:
Давайте заметим, что мы заранее знаем в какие отрезки времени ребра дерева будут включены/выключены. Тогда решение будет практически такое же, как и у известной задачи "Dynamic connectivity Problem offline". Пишем за пол часа, не ошибаемся и получаем сотку.
❤️
А:
Нас просят для каждой вершины посчитать до скольких вершин мы сможем дойти так, что ни на каком префиксе ксор на пути не был равен 0.
Это значит, что мы не можем идти дальше, если придем в вершину, до которой ксор на пути равен 0.
То, что ксор на пути между вершинами равен 0 значит, что ксоры на пути от этих вершин до корня равны.
Простое решение с сложной структурой данных:
Давайте сначала соединим все вершины ребрами.
Будем перебирать различные ксоры на путях до корня.
Давайте для фиксированного ксора уберем все из графа все ребра, которые содержат вершины с таким ксором.
Затем для каждой вершины с таким ксором посчитаем сумму размеров компонент, с которыми она была связана изначально и это будет ответ(так как в компонентах не будет вершин с таким ксором, мы сможем дойти до каждой вершины из компоненты).
Потом снова добавим ребра.
Это можно сделать с помощью структуры данных "линк кат три".
Решение без сложной структуры данных:
Давайте заметим, что мы заранее знаем в какие отрезки времени ребра дерева будут включены/выключены. Тогда решение будет практически такое же, как и у известной задачи "Dynamic connectivity Problem offline". Пишем за пол часа, не ошибаемся и получаем сотку.
Что и когда решать?
Лонгрид о том, как грамотно распределять время между олимпиадами.
Привет, Сборник! Сегодня я хочу рассказать вам о расписании, причем не о расписании дня, а такого, более глобального(месяц/год).
Итак, многие часто говорят о важности расписания дня, что важно кушать, спать и т.д., но ведь важная часть этого всего - бот олимпиад и задач и возникает вопрос: что и когда решать?
Первое о чем хочется сказать — продолжительные отборочные и заключительные туры. У туров, которые идут долго, важно не решать все в один день. Понятно, что решать их на протяжении всего тура тоже не получится. Я, спустя несколько лет, пришел к тому, что удобнее и продуктивнее выделить несколько дней в начале, возможно заходить их решать в середине (буквально по 1-2 дня тратить) и в конце уже, когда обдумал по дороге задачи в какой-то степени, оставить +- недельку (зависит от олимпиады) и закрыть то, что можешь закрыть.
Дальше есть важный момент — пересечение олимпиад. Часто туры (особенно отборочные) любят проводить в один день, по крайней мере я с таким столкнулся. В таких случаях приходится выбирать, что именно писать. Важно понимать, что не стоит просто всегда выбирать олимпиаду, которая престижнее. Например, если обе олимпиады дают БВИ, но одна проще и менее "престижна", то лучше написать именно ее, потому что будет проще ее взять, ведь как никак изначально все эти олимпиады мы пишем для поступления. Но понятно, что такие выборы в пользу более слабых олимпиад стоит делать, если в сильной ты не уверен на 100%.
Также, не стоит гнаться за всем и сразу. Да, стоит выбрать побольше олимпиад и писать их. Но при этом стоит из них выделить 3-4 олимпиады, к которым готовиться ты будешь особенно готовится. Потому что выиграть все можно, но для этого надо быть сильно умнее, чем остальные. А выиграть конкретные олимпиады 1-2 уровня можно и не будучи таким гением.
Ну и пожалуй самая важная часть всего этого - это распределить время бота и не пропустить олимпиады(!). А значит за своими олимпиадами надо следить и не упустить даты. Решая этот вопрос, по началу, я старался их запоминать, но это в какой-то момент это стало слишком неудобно. Тогда появилась таблица, с которой стало гораздо проще. Довольно хороший способ, в следующем году я ее переделал и тогда ей стали пользоваться и мои друзья в том числе. Вести свою таблицу довольно удобно, но хотелось бы как-то автоматизировать это все, чтобы не приходилось постоянно за этим следить и сидеть на нервах от того что можешь пропустить что-то (а еще хуже реально это пропустить).
Так вот теперь хочется поделится одним ботом, который сильно упрощает эту задачу. В нем можно выбрать свои олимпиады и получать уведомления о турах и т.п. Можно смотреть известные даты по своим олимпиадам. В общем, это то, чего мне не хватало в свое время, а значит может помочь и вам.
Автор: Антон Витюк
Крайне полезный бот: https://t.me/OlimpHelperBot
Немного о моих успехах:
Студент ПМИ МФТИ
Высшая проба - Победитель
Innopolis Open - Призер
МОШ - Победитель
ИОИП - Призер
Технокубок - Победитель
Когнитивные технологии - Победитель
Всесибирская - Победитель
Теги: #рекомендации
Лонгрид о том, как грамотно распределять время между олимпиадами.
Привет, Сборник! Сегодня я хочу рассказать вам о расписании, причем не о расписании дня, а такого, более глобального(месяц/год).
Итак, многие часто говорят о важности расписания дня, что важно кушать, спать и т.д., но ведь важная часть этого всего - бот олимпиад и задач и возникает вопрос: что и когда решать?
Первое о чем хочется сказать — продолжительные отборочные и заключительные туры. У туров, которые идут долго, важно не решать все в один день. Понятно, что решать их на протяжении всего тура тоже не получится. Я, спустя несколько лет, пришел к тому, что удобнее и продуктивнее выделить несколько дней в начале, возможно заходить их решать в середине (буквально по 1-2 дня тратить) и в конце уже, когда обдумал по дороге задачи в какой-то степени, оставить +- недельку (зависит от олимпиады) и закрыть то, что можешь закрыть.
Дальше есть важный момент — пересечение олимпиад. Часто туры (особенно отборочные) любят проводить в один день, по крайней мере я с таким столкнулся. В таких случаях приходится выбирать, что именно писать. Важно понимать, что не стоит просто всегда выбирать олимпиаду, которая престижнее. Например, если обе олимпиады дают БВИ, но одна проще и менее "престижна", то лучше написать именно ее, потому что будет проще ее взять, ведь как никак изначально все эти олимпиады мы пишем для поступления. Но понятно, что такие выборы в пользу более слабых олимпиад стоит делать, если в сильной ты не уверен на 100%.
Также, не стоит гнаться за всем и сразу. Да, стоит выбрать побольше олимпиад и писать их. Но при этом стоит из них выделить 3-4 олимпиады, к которым готовиться ты будешь особенно готовится. Потому что выиграть все можно, но для этого надо быть сильно умнее, чем остальные. А выиграть конкретные олимпиады 1-2 уровня можно и не будучи таким гением.
Ну и пожалуй самая важная часть всего этого - это распределить время бота и не пропустить олимпиады(!). А значит за своими олимпиадами надо следить и не упустить даты. Решая этот вопрос, по началу, я старался их запоминать, но это в какой-то момент это стало слишком неудобно. Тогда появилась таблица, с которой стало гораздо проще. Довольно хороший способ, в следующем году я ее переделал и тогда ей стали пользоваться и мои друзья в том числе. Вести свою таблицу довольно удобно, но хотелось бы как-то автоматизировать это все, чтобы не приходилось постоянно за этим следить и сидеть на нервах от того что можешь пропустить что-то (а еще хуже реально это пропустить).
Так вот теперь хочется поделится одним ботом, который сильно упрощает эту задачу. В нем можно выбрать свои олимпиады и получать уведомления о турах и т.п. Можно смотреть известные даты по своим олимпиадам. В общем, это то, чего мне не хватало в свое время, а значит может помочь и вам.
Автор: Антон Витюк
Крайне полезный бот: https://t.me/OlimpHelperBot
Немного о моих успехах:
Студент ПМИ МФТИ
Высшая проба - Победитель
Innopolis Open - Призер
МОШ - Победитель
ИОИП - Призер
Технокубок - Победитель
Когнитивные технологии - Победитель
Всесибирская - Победитель
Теги: #рекомендации
Оцените новое лого👇👇👇
Решил провести небольшой ребрендинг!
Решил провести небольшой ребрендинг!
Решето Эратосфена
Ссылка на статью: https://teletype.in/@timofeyizhitskiy/2XsHxDRVYrn
Автор: Тимофей Ижицкий
Теги: #методы #алгоритмы #математика #решетоэратосфена
Ссылка на статью: https://teletype.in/@timofeyizhitskiy/2XsHxDRVYrn
Автор: Тимофей Ижицкий
Теги: #методы #алгоритмы #математика #решетоэратосфена
Teletype
Решето Эратосфена
Решето Эратосфена
Как выиграть ВСОШ по информатике
Наткнулся на интересную статью, посвященную подготовке к ВСОШ. В Сборнике было достаточно много разных рекомендаций от разных олимпиадников, но лишним это уж точно не будет. Чем больше разных методов и фактов ты знаешь, тем тебе легче готовиться. А главное — готовится грамотно.
Статья подойдет как новичкам, так и продвинутым олпрогерам!
Ссылка на статью: https://habr.com/ru/articles/720840/
Теги: #рекомендации
Наткнулся на интересную статью, посвященную подготовке к ВСОШ. В Сборнике было достаточно много разных рекомендаций от разных олимпиадников, но лишним это уж точно не будет. Чем больше разных методов и фактов ты знаешь, тем тебе легче готовиться. А главное — готовится грамотно.
Статья подойдет как новичкам, так и продвинутым олпрогерам!
Ссылка на статью: https://habr.com/ru/articles/720840/
Теги: #рекомендации
25 ноября стартует длинный отборочный тур XVIII открытой олимпиады по программированию!
Расписание олимпиады:
— Длинный тур: 25 ноября 2023 года - 15 января 2024 года
— Финал олимпиады: 7-9 марта 2024 года
25 числа еще раз вас об этом оповестим. Готовимся решать крутые задачи!
Теги: #олимпиады
Расписание олимпиады:
— Длинный тур: 25 ноября 2023 года - 15 января 2024 года
— Финал олимпиады: 7-9 марта 2024 года
25 числа еще раз вас об этом оповестим. Готовимся решать крутые задачи!
Теги: #олимпиады
Чат
Также напоминаю, что у Сборника есть чат, в котором вы можете помогать друг другу.
В чате есть одно строгое правило: не обсуждать задачи текущих олимпиад, а также не сливать решения на эти задачи.
Приглашаем: https://t.me/shornik_olprog_chat
Также напоминаю, что у Сборника есть чат, в котором вы можете помогать друг другу.
В чате есть одно строгое правило: не обсуждать задачи текущих олимпиад, а также не сливать решения на эти задачи.
Приглашаем: https://t.me/shornik_olprog_chat
Forwarded from Innopolis Open // Informatics // 2023/24
Уважаемые участники олимпиады Innopolis Open, добрый день!
Мы внимательно изучили обратную связь, которую вы дали нам по итогам проведения первого отборочного этапа по направлению «Информатика».
Сложности, возникшие во время отборочного этапа, были связаны с изменениями в процедуре проверки заданий во время тура, временем проверки решений и невозможностью получить доступ к детализации по группам тестов.
На текущий момент большая часть пунктов по вашей обратной связи была устранена командой All Cups. На следующих соревнованиях вы сможете увидеть эти улучшения.
Команда организаторов Innopolis Open также скорректирует процесс подготовки заданий, чтобы следующие туры прошли для вас комфортно и бесшовно.
Пока идет процесс внесения необходимых улучшений на платформе All Cups, организаторы олимпиады приняли решение о переводе следующих этапов олимпиады на другую платформу.
До встречи на следующих этапах и соревнованиях!
Мы внимательно изучили обратную связь, которую вы дали нам по итогам проведения первого отборочного этапа по направлению «Информатика».
Сложности, возникшие во время отборочного этапа, были связаны с изменениями в процедуре проверки заданий во время тура, временем проверки решений и невозможностью получить доступ к детализации по группам тестов.
На текущий момент большая часть пунктов по вашей обратной связи была устранена командой All Cups. На следующих соревнованиях вы сможете увидеть эти улучшения.
Команда организаторов Innopolis Open также скорректирует процесс подготовки заданий, чтобы следующие туры прошли для вас комфортно и бесшовно.
Пока идет процесс внесения необходимых улучшений на платформе All Cups, организаторы олимпиады приняли решение о переводе следующих этапов олимпиады на другую платформу.
До встречи на следующих этапах и соревнованиях!
ЗЭ ВСОШ пройдет в Татарстане!
Даты: 6 апреля — 11 апреля
Даты: 6 апреля — 11 апреля
Метод сканирующей прямой (scanline).
Пререквизиты:
🔙 Уметь сортировать по своему компаратору
Теория:
📚 Алгоритмика - описание, примеры задач, реализация на C++
📼 Лекция Влада Невструева с Rucode - описание, примеры задач, реализация на C++
📼 Лекция Филлипа Руховича с Rucode - описание, примеры задач, реализация на C++ (здесь побольше задач)
Первые задачи:
💻 Informatics 1
💻 Informatics 2
💻 ACMP 1 - сразу скажу, тут без ДО можно спокойно решить
KIT контест по теме с периодически пополняемыми задачами:
🔄 Контест - сейчас там пока 5 задач, но будт еще. Для решения нужно вступить в группу на кф - ссылка
Вопросы на понимание темы:
❓ Что нужно учитывать при написании своего компаратора?
❗️ 1. Он должен быть ассиметричным, то есть: если comp(a, b) == true тогда comp(b, a) == false 2. Обладать транзитивностью, то есть: если comp(a, b) == true и comp(b, c) == true тогда comp(a, c) == true. Чуть подробнее в доке
❓ Как может пригодиться сортировать точки на плоскости в задачах?
❗️ Самое очевидное - по x или y. Также, в задачах часто встречается сортировка по (полярному) углу относительно точки. Есть и алгоритмы, которые используют такую сортировку, например, алгоритм Грэхэма поиска выпуклой оболочки
❓ Допустим у нас есть задача, где даны объекты и они никак не меняются. Нужно ответить на запросы про них. При чем тут сканлайн?
❗️ Раз объекты не меняются, то можно получить ответы на запросы не в порядке их появления во входных данных, а в любом удобном нам (но не забыть потом вывести в нужном порядке). Про это говорят "отвечать в оффлайне". Тогда можно подумать про то, чтобы отсортировать как-то эти запросы и попробовать решить задачу сканлайном
Делитесь с друзьями, задачи будут интересны любому уровню!
💬 Следующие темы смело предлагайте в комментариях. Также, делитесь интересными задачами и материалами по этой теме!
Автор: https://t.me/KogutIvanTutoring
Пререквизиты:
🔙 Уметь сортировать по своему компаратору
Теория:
📚 Алгоритмика - описание, примеры задач, реализация на C++
📼 Лекция Влада Невструева с Rucode - описание, примеры задач, реализация на C++
📼 Лекция Филлипа Руховича с Rucode - описание, примеры задач, реализация на C++ (здесь побольше задач)
Первые задачи:
💻 Informatics 1
💻 Informatics 2
💻 ACMP 1 - сразу скажу, тут без ДО можно спокойно решить
KIT контест по теме с периодически пополняемыми задачами:
Вопросы на понимание темы:
Автор: https://t.me/KogutIvanTutoring
Please open Telegram to view this post
VIEW IN TELEGRAM
Друзья, хочу напомнить, что каждый из вас может написать пост в Сборник! Все предельно просто, прилагаю алгоритм публикации:
— Придумать тему поста
— Написать мне в личные сообщения
— Согласовать публикацию
— Подготовить пост
— Пройти небольшую модерацию и сделать правки
— Опубликоваться по графику постов Сборника
Поделись со всем комьюнити своими идеями и получи ценный фидбек. Прояви себя!
— Придумать тему поста
— Написать мне в личные сообщения
— Согласовать публикацию
— Подготовить пост
— Пройти небольшую модерацию и сделать правки
— Опубликоваться по графику постов Сборника
Поделись со всем комьюнити своими идеями и получи ценный фидбек. Прояви себя!
Сборник Олпрогера pinned «Друзья, хочу напомнить, что каждый из вас может написать пост в Сборник! Все предельно просто, прилагаю алгоритм публикации: — Придумать тему поста — Написать мне в личные сообщения — Согласовать публикацию — Подготовить пост — Пройти небольшую модерацию и…»
Задачи по темам
Откопал достаточно старую публикацию на Codeforces, в которой хорошие задачи собранны по темам. Не рекомендуется решать задачу, когда вы знаете, что в ней нужно применять(тут можно сделать куча оговорок, но суть вы уловили), но для нарабатывания навыка использования алгоритма это может пригодится. Пользуйтесь!
Ссылка: https://codeforces.com/blog/entry/55274
Теги: #задачи #алгоритмы
Откопал достаточно старую публикацию на Codeforces, в которой хорошие задачи собранны по темам. Не рекомендуется решать задачу, когда вы знаете, что в ней нужно применять(тут можно сделать куча оговорок, но суть вы уловили), но для нарабатывания навыка использования алгоритма это может пригодится. Пользуйтесь!
Ссылка: https://codeforces.com/blog/entry/55274
Теги: #задачи #алгоритмы
Codeforces
Problem Topics
Good Day to you!