Educational Codeforces Round 143 [рейтинговый для Div. 2] Привет, Codeforces! В [contest_time:1795] состоится [contest:1795]. Продолжается серия образовательных раундов в рамках инициативы [Harbour.Space University](https://harbour.space/)! Подробности о сотрудничестве [Harbour.Space University](https://harbour.space/) и Codeforces можно прочитать <a href="http://mirror.codeforces.com/blog/entry/51208">в посте</a>. Этот раунд будет **рейтинговым для участников с рейтингом менее 2100**. Соревнование будет проводиться по немного расширенным правилам ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования. Вам будет предложено **6 или 7 задач на 2 часа**. Мы надеемся, что вам они покажутся интересными. Задачи вместе со мной придумывали и готовили Адилбек [...

Full text and comments »

[Tutorial] Пересечение матроидов простыми словами **[This article is also available in [English](https://mirror.codeforces.com/blog/entry/69287?locale=en)]** Привет, CodeForces. Я думаю, что матроиды &mdash; это прекрасные и очень мощные структуры, однако, не настолько хорошо известные в спортивном программировании. Я познакомился с матроидами на Зимних Петрозаводских Сборах 2019. Там была задача, которая очевидно не решалась обычными способами, известными мне тогда. Разбор этой задачи состоял буквально из трех слов “just matroid intersection”. Тогда мне потребовалось больше двух дней дорешивания чтоб найти всю необходимую информацию и детали и написать решение, которое получает Accepted. И намного больше времени мне потребовалось чтобы понять почему это действительно работает и как именно это работает. (Я до сих пор сомневаюсь в некоторых деталях.) Конечно, совершенно не трудно нагуглить все необходимые определения и статьи, связанные с этой темой, но мне кажется, что все они больше сконцентрированы на математической теории, с...

Full text and comments »

Два вида динамического программирования: Симуляция процесса Привет! Я получил хороший отлкик от сообщества Codeforces, поэтому я начинаю серию обучающих постов. Сегодня я хочу рассказать об одной очень полезной классификации задач на динамическое программирование, к которой я пришёл за годы практики. Я не претендую на авторство этой идеи, но я ни разу не видел, чтобы она где-то явно выражалась, так что я введу собственные термины. Назовём это _"ДП по подзадачам"_ (или _"Обычное ДП"_) и _"ДП с симуляцией процесса"_. Сегодня я сосредоточусь на последнем. ### Обычный подход Как вам рассказали о ДП? В каких терминах? Когда я учился в школе, мне объяснили, что ДП – это просто разбиение задачи на подзадачи. Сначала вы вводите параметры в задачу. Набор значений по каждому параметру называется _состоянием_ ДП, оно соответствует конкретной подзадаче. Затем вам всего лишь надо найти ответ для каждого состояния / подзадачи, и знание ответа для меньших подзадач должно помочь вам найти ответ для текущей. Рассмотрим пример: [AtCoder DP Contest: З...

Full text and comments »

Как я учился в бакалавриате ПМИ Питерской Вышки Привет, codeforces! Меня зовут Миша, в этом году я закончил бакалавриат НИУ ВШЭ — Санкт-Петербург по специальности “[Прикладная математика и информатика](https://spb.hse.ru/ba/appmath/)” (ПМИ) и хочу поделиться своими впечатлениями. Немного о себе: в школе я много решал задачи на codeforces, участвовал в олимпиадах и даже занял [третье место](http://neerc.ifmo.ru/school/archive/2015-2016/ru-olymp-roi-2016-standings.html) на РОИ 2016. Окончив школу, я хотел выбрать вуз, который поможет мне построить успешную карьеру в сфере IT. Я пообщался со старшими товарищами и решил поступать в Академический Университет, где на тот момент уже давно существовала прекрасная магистерская программа и два года как появилась бакалаврская программа, которой студенты были очень довольны. Вышло так, что по окончании второго курса наша кафедра переехала из Академического Университета в петербургский кампус Высшей Школы Экономики. Все очень переживали, как пройдет этот переезд, но, к счастью, всё [сл...

Full text and comments »

Educational Codeforces Round 140 [рейтинговый для Div. 2] Привет, Codeforces! В [contest_time:1767] состоится [contest:1767]. Продолжается серия образовательных раундов в рамках инициативы [Harbour.Space University](https://harbour.space/)! Подробности о сотрудничестве [Harbour.Space University](https://harbour.space/) и Codeforces можно прочитать <a href="http://mirror.codeforces.com/blog/entry/51208">в посте</a>. Этот раунд будет **рейтинговым для участников с рейтингом менее 2100**. Соревнование будет проводиться по немного расширенным правилам ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования. Вам будет предложено **6 или 7 задач на 2 часа**. Мы надеемся, что вам они покажутся интересными. Задачи вместе со мной придумывали и готовили Адилбек [...

Full text and comments »

Отчет о деятельности Botan Investments за апрель. Классификация очень простых задач для массовых олимпиад Всем привет! В апреле в грантовой программе **Botan Investments** приняли участие преподаватели 21 вуза. Больше всего студентов удалось привлечь к тренировкам в Иркутском ГУ (23 человека). Больше всего тренировок (восемь) провели в Кубанском ГТУ, Саратовском ГУ и Мордовском ГУ. В нашей группе ВК можно найти [новый пост Михаила Рубинчика](https://vk.com/botaninvestments?w=wall-115220257_404) со списком того, что необходимо сделать, чтобы создать крутое олимпиадное сообщество в регионе/городе/образовательном учреждении. А сегодняшний пост посвящен массовости олимпиад и подготовке задач для новичков. <br> <p style="background-color: rgb(250,250,250);padding: 1.0em 1.0em;"> Сегодня я хочу немного поговорить про массовость олимпиад и более подробно про подготовку задач для новичков. Я во многих своих постах говорю, что рост числа участников олимпиад &mdash; это важно, и перечисляю, как нам этого добиться. Комментаторы часто с этим не согласны, но я продолжаю гнуть свою линию и наст...

Full text and comments »

Олимпиадные задачи по программированию: что за зверь? _Друзья, недавно в нашем Хаброблоге мы опубликовали [пост](http://habrahabr.ru/company/abbyy/blog/176421/) о том, что же вообще представляет из себя задача спортивного программирования. Изначально пост предполагал сравнение олимпиадных задач с задачами реальной разработки. Однако в финальном варианте мы решили исключить аналогии с промышленным программированием. Будет интересно почитать в комментариях примеры ваших подобных сравнений :)_ "Недавно мы анонсировали конкурс задач по спортивному программированию. Организаторы конкурса попросили написать короткое объявление о конкурсе в блог ABBYY, но строгий редактор отказался печатать анонс без объяснения того, что же такое олимпиадная задача. Из этого родилась целая статья. Начнем, пожалуй, с [ ](http://mirror.codeforces.com/contest/211/problem/E) олимпиадной задачи. Первое, что бросается в глаза, это необычное условие. Такой подход сложился исторически: писать краткую математическую формулировку не принято. Обычно ее пытаются связать с р...

Full text and comments »

Нововведения: друзья, теги и прочее <p> Всем привет! </p> <p> Как многие могли заметить, недавно в рейтинге пользователей появилась закладка "Рейтинг друзей". Но это лишь первое из ряда улучшений, сделанных по вашим заявкам и не только. Теперь вы можете просматривать список друзей и команд с их участием в архиве задач, списке зарегистрированных на контест и в списке лидеров по вкладу. В связи с неуклонным ростом числа пользователей Codeforces (и, соответственно, размера страницы рейтинга) на ней был введён постраничный просмотр. Механизм подбора доступных для перехода страниц также был усовершенствован: теперь всегда доступны первая, последняя и несколько соседних с текущей. </p> <p> Но и это ещё не всё. Для классификации и более удобного поиска задач было решено ввести возможность добавлять к ним теги. Поиск ещё не реализован, однако администраторы и пользователи с высоким (цвет хэндла должен быть как минимум синим) рейтингом,&nbsp; решившие задачу, могут добавлять теги уже сейчас. Для этого достаточно открыт...

Full text and comments »

IOI 2013, 1 тур Первый тур никак не может начаться :( Сейчас уже доступна [видео-трансляция](http://new.livestream.com/accounts/4506465/ioi2013) (говорят зацикленная) Мы надеемся, что с началом контеста появятся результаты. Через некоторое время после начала контеста, мы выложим условия и будем рады их обсудить. **UPD** [Scoreboard](http://live.ioi2013.org/Ranking.html) За происходящим будем следить мы с [user:powerful.aloe,2013-07-08]. 8.53 Контест должен был начаться в 8:00, но из-за технических проблем участников только запустили. Обещают начать в 9:00 по местному. 9.01 Участников куда массово повели. Что там вообще происходит? 9.02 Вроде все вернулись. У одного из участников мы заметили 4 минуты да начала контеста на мониторе. 9.11 Видимо отложили еще. Или не отложили. Никто ничего не говорит. 9.25 На трансляции наконец-то показали участников. Контест уже идет. Интересно, когда он начался? 9.31 Вроде обещают сделать табличку в ближайшее время. Тем временем ~KOTEHO...

Full text and comments »

Классификация задач <p> <p><strong>Добрый день всем.</strong></p> <p align="justify">Я учусь в Таганрогском Технологическом Институте ЮФУ, и так уж сложилось, что олимпиадная база, а точнее средний уровень команд, у нас не так высок как хотелось бы (тем не менее, спасибо тем, кто вкладывает в ее развитие собственные силы и время). Так что мы работаем над оптимальным вариантом проведения тренировок. К какому-то моменту я понял, что беспорядочное решение задач не самый эффективный способ повышения навыков, и считаю, что лучший вариант для меня на моем уровне (да и для нашей команды) – решать по нескольку задач на каждую тему. Проблема в том, что по поводу этих самых тем я имею несколько размытое представление.</p> <p align="justify">Суть вопроса в следующем, <strong>на какие темы стоит решать задачи, и где их брать</strong> (в смысле задачи на конкретные темы)? Под темой я понимаю не в широком смысле "комбинаторику" например, а более узкие (если ту же "комбинаторику" реально разбить на такие)....

Full text and comments »

Задача на поиск (тянки) **Ищу тянку** Определения: 1. Определение бесконечно малой последовательности. 2. Определение сходящейся последовательности. 3. Определение монотонной последовательности. 4. Определение предельной точки последовательности. 5. Определение подпоследовательности. 6. Определение верхнего и нижнего пределов последовательности. 7. Определение фундаментальной последовательности. 8. Определение предела функции. 9. Определение монотонной функции. 10. Определение непрерывности функции. 11. Определение сложной функции. 12. Определение предела функции по Коши и по Гейне. 13. Определение производной и дифференциала Остальное: 1. Множества. Множество действительных чисел, его подмножества. 2. Функция от одной действительной переменной, ее область определения. График функции. Способы задания. 3. Специальные способы задания функций (сложная, параметрически заданная функция, обратная функция). Сложные и обратные функции. 4. Числовая последовательность и ее предел. Теорема об ...

Full text and comments »

УрФУ. Как мы внедрили программирование в курс алгебры Всем привет! В данном посте я расскажу про то, как студенты УрФУ программируют в курсе алгебры. Этот курс несколько лет используется на ФИИТ УрФУ, а с 2023 года будет использоваться в новом [алгоритмическом бакалавриате](https://uralsp.ru/algorithm_bachelor?utm_source=cf_algebra). Для начала я дам слово одному из тренеров по спортивному программированию в УрФУ Дмитрию Косолобову: _— Давным-давно, в 2007 году, я слушал алгебру на первом курсе в УрФУ (тогда еще УрГУ). И мы с одногруппниками-олимпиадниками ворчали (между собой, т.к. преподавателю сказать боялись, да и не думали, что это что-то изменит) на разные аспекты преподавания. Среди «ворчунов» был Алексей Ефремов — победитель ВсОШ по информатике и Михаил Рубинчик — призер ВсОШ, а сейчас тренер УрФУ по спортивному программированию, как и я. Сам я олимпиадником не был и не являюсь, моя основная деятельность — наука и преподавание._ _Самые серьезные проблемы алгебры тех лет — это огромное количество арифметических действий...

Full text and comments »

ABBYY Cup 2.0 — Hard: разбор Разбор задач будет пополняться :) ### Разбор задачи <<Развивающая игра>> Это была самая простая задача из сложного набора. Для начала заметим, что можно решать данную задачу для каждого элемента $a_i$ отдельно. То есть, если мы фиксируем некоторое $k$, то вклад каждого $a_i$ в ответ можно считать отдельно. Итак, фиксируем некоторое $a_i$. Найдем максимально возможное $j$ такое, что $i+2^j \le n$. Несложно видеть, что для всех $k < i + 2^j$ вклад $a_i$ в ответ будет равен $a_i$. То есть нужно будет сделать $a_i$ ходов с переходом в $a_{i+2^j}$. Далее найдем такое максимальное $u$, что $2^j+2^u \le n$. Заметим, что $u < j$. Также заметим, что для всех $k$ таких, что $i+2^j \le k < i+2^j+2^u$ вклад $a_i$ в ответ будет равен $2 \cdot a_i$. Далее найдем такое $q$, что $i+2^j+2^u+2^q \le n$. Итак, для каждого элемента $a_i$ мы должны найти соответствующую последовательность степеней двойки. Очевидно, что общая сложность этого процесса $O(n \cdot \log(n))$. Теперь нам нужно с...

Full text and comments »

Отчет о деятельности Botan Investments за ноябрь + интервью с тренером команд Мордовского ГУ Натальей Плотниковой В ноябре фонд Виктора Шабурова Botan Investments выступил [одним из спонсоров сборов по программированию на базе МФТИ Moscow International Workshop ACM ICPC 2016](http://mirror.codeforces.com/blog/entry/48301), также была оказана финансовая поддержка трем командам (САФУ, СГУ, ТПУ), благодаря которой ребята смогли приехать на сборы. В этом месяце в грантовой программе фонда приняли участие преподаватели из 18 университетов. Больше всего студентов пришли на тренировки в Саратовском ГУ (31 активный участник), а больше всего тренировок провели в Саратовском ГУ (тренер Михаил [user:MikeMirzayanov,2016-12-01] Мирзаянов) и Мордовском ГУ (тренер Наталья [user:linsierra,2016-12-01] Плотникова). А еще к нам присоединился новый вуз &mdash; СОГУ им. К. Л. Хетагурова. В группе Botan Investments ВК выходят новые посты Михаила [user:MikhailRubinchik,2016-12-01] Рубинчика. Можно почитать про [основные соревнования, на которые надо ездить](https://vk.com/botaninvestments?w=wall-115220257_61) и [на как...

Full text and comments »

Записки юного пациента. Все части, год спустя. Краткое предисловие: Год назад лежал в больнице №** в городе N c черепно-мозговой травмой. Скатился с горы на плюшке, влетел в бревно, лежащее возле дороги. Но я не дурак, чтобы просто скатываться неизвестно где. На то была причина. Дело в том, что в процессе подъема на гору после n-ого спуска я решил подняться по другой стороне и увидел лежащие бревна. Решил предложить друзьям убрать эти деревья, чтобы никто не влетел. Друзья встретили меня наверху. Я в двух словах объяснил, что надо сделать. Они поехали быстрее меня. Я испугался за них, они могли не увидеть бревна и влететь в них. Поэтому я разогнался, чтобы обогнать их, и влетел. Отвечал на вопросы друзей абсолютно вменяемо, но ничего ровным счетом не помню. Не помню также как и в скорую поднимался в гору. 21.01.12 "Со вчерашнего вечера нового соседа завезли.Он попал сюда из-за разборок с женой."Бьёт значит любит" — это не тот случай.Жена сначала ударила стеклянной бутылкой по голове мужа, после выхватила нож.Муж был безору...

Full text and comments »