Codeforces Round #295: разбор (теперь с бонусами!) Мы хотели бы также поблагодарить тестеров задач этого раунда и олимпиады ЗКШ: [user:alger95,2015-03-02], [user:thefacetakt,2015-03-02], [user:adamant,2015-03-02], [user:dragonic,2015-03-02], [user:Who179,2015-03-02], [user:ASverdlov,2015-03-02]. Пожалуйста, пишите в комментариях о найденных ошибках. **UPD**: я вспомнил, что забыл написать регулярные бонусные челленджи. Так что вот, пожалуйста. [problem:520A] Идея:[user:Endagorion,2015-03-02] Подготовка:[user:Endagorion,2015-03-02] Чтобы проверить, что все буквы присутствуют, заведем массив длины 26 и для каждой буквы поставим в соответствующую ячейку единичку. В конце надо проверить, что все 26 единичек на месте. Решение работает за $O(n)$. Также надо не забыть перевести все буквы к нижнему регистру (или наоборот, все буквы к верхнему). Чтобы перевести буквы в нижний регистр, можно использовать встроенные функции, например, `tolower` в Python. Также можно пользоваться тем, что буквы от `a` до `z` идут подряд по их ...

Full text and comments »

Codeforces Round #295 Привет, Codeforces! [2 марта в 10:00 MSK](http://www.timeanddate.com/worldclock/fixedtime.html?day=2&month=3&year=2015&hour=10&min=0&sec=0&p1=166) состоится раунд #295 для участников из обоих дивизионов. Раунд состоится практически одновременно с олимпиадой [Зимней Компьютерной Школы] (http://it-edu.mipt.ru/ru/zksh2015) на схожем комплекте задач. Авторы задач — я ([user:Endagorion,2015-03-01]) и Евгений Савинов ([user:savinov,2015-03-01]). В подготовке задач принимали участие члены технического комитета Зимней Компьютерной школы: Георгий Чебанов ([user:gchebanov,2015-03-01]), Филипп Рухович ([user:DPR-pavlin,2015-03-01]), Александр Машрабов ([user:map,2015-03-01]), Сергей Киян ([user:sokian,2015-03-01]), Константин Семенов ([user:zemen,2015-03-01]), Кинан Альсармини ([user:Sarkin,2015-03-01]). Спасибо Максиму Ахмедову ([user:Zlobober,2015-03-01]) за помощь в подготовке задач, Марии Беловой ([user:Delinur,2015-03-01]) за перевод условий на английский язык, Михаилу Мирзаян...

Full text and comments »

Школьная индивидуальная олимпиада #1 (ЗКШ 2010/11) - Codeforces Beta Round #38 (ACM-ICPC Rules) Всем доброго времени суток<br><br>Завтра, 30 октября я приглашаю Вас принять участие в увлекательном соревновании. Оно будет являться отборочным раундом в ЗКШ (<b><i>Школьная индивидуальная олимпиада #1 (ЗКШ 2010/11)</i></b>, подробнее читайте <a href="http://codeforces.me/blog/entry/753">тут</a>), но для более взрослых участников это будет просто новым Codeforces раундом (<b><i>Codeforces Beta Round #38, ACM-ICPC Rules</i></b>).<br><br>Замечу, что в отличие от предыдущей отборочной олимпиады, наше завтрашнее соревнование - личное. Официальные правила соревнования, как видно из названия, - ACM-ICPC.<br><br>За это соревнование, как и обычно, будет начисляться рейтинг. Участники, которые не принимают участие в отборе в ЗКШ, будут в таблице результатов отображаться, как участники "вне конкурса", но не пугайтесь, рейтинг будет подсчитан по <u>совмещенной</u> таблице.<br><br>Также, после совещания жюри, было решено продлить раунд. Теперь он будет длиться <b>4 часа</b>, обратите на это внима...

Full text and comments »

Итоги заочных олимпиад ЗКШ <img src="http://assets.codeforces.com/images/baloons.png" style="float: left; margin: 0pt 1em;"> <p> Как принято говорить в таких случаях: "Вот и закончилась серия заочных школьных олимпиад ЗКШ 2010/2011!" </p> <p> Все олимпиады серии проводились при поддержке компаний <a href="http://yandex.ru">Yandex</a> и <a href="http://abbyy.ru">ABBYY</a>. Было проведено 6 соревнований: 3 командных олимпиады и 3 индивидуальных. Самое время подвести итоги и выявить победителей олимпиады. Результаты по двум номинациям (командной и личной) подводились отдельно - в каждой из них для участников брались в расчет результаты двух лучших выступлений из трех. Вот ссылки на суммарные результаты по каждой номинации: </p> <ul> <li><a href="http://codeforces.me/summary/zksh-2011-teams">результаты командных олимпиад</a></li> <li><a href="http://codeforces.me/summary/zksh-2011-individuals">результаты индивидуальных олимпиад</a></li> </ul> <p> Всего на серию было зарегистрировано около 750 ...

Full text and comments »

Школьная командная олимпиада #3 (ЗКШ 2010/11) <p>Школьная командная олимпиада #3 (ЗКШ 2010/11) состоится <a href="http://timeanddate.com/worldclock/fixedtime.html?day=13&amp;month=11&amp;year=2010&amp;hour=14&amp;min=0&amp;sec=0&amp;p1=166">13 ноября, в 14:00 по Москве</a>. Это заключительное командное соревнование из серии, будем рады видеть как постоянных участников, так и новые команды. </p> <p>Раунд был подготовлен мной, Артемом Раховым, Николаем Кузнецовым и Иваном Фефером. Все мы совсем скоро отправимся на полуфинал в Петербург, а сейчас ребята совмещают подготовку к полуфиналу с составлением контестов. Special thanks за переводы задач Марии Беловой.</p> <p>Напоминаю, что все желающие смогут принять участие в нем вне конкурса. Решайтесь :)</p> <p><a href="http://codeforces.me/summary/zksh-2011-teams">Суммарные результаты</a> по контестам мы решили подводить по системе ИТМО, в соответствии с которой команда получает балл от 0 до 200 за каждое соревнование. Из трех контестов будут зачтены два лучших выступления, резу...

Full text and comments »

Зимняя Компьютерная Школа 2015  С 24 февраля по 6 марта 2015 года в г. Долгопрудном (Московская область) на базе московского Физтеха пройдет шестая **Зимняя компьютерная школа (ЗКШ-2015)** для школьников 9-11 классов. **В программе ЗКШ-2015:** - Ежедневные учебные контесты: подготовка к финалу Открытой олимпиады, финалам национальных олимпиад по программированию. - Олимпиады по информатике и программированию, математике. - Лекции сотрудников базовых организаций ФИВТ о реальных задачах в IT-индустрии. - Лекции профессиональных ученых по комбинаторной математике. - Спортивные и интеллектуальные игры. **Учебный процесс.** По результатам вступительного контеста, который пройдет в первый день, участники будут разбиты на 3 потока. Далее в ЗКШ будет 6 обычных учебных дней, включающих в себя контест и разбор в первой половине дня, а также несколько лекций (по алгоритмам и структурам данных,...

Full text and comments »

Школьная индивидуальная олимпиада #3 (ЗКШ 2010/11) - Codeforces Beta Round #45 (ACM-ICPC Rules) <p style="margin: 1em 0px; padding: 0px; font-family: verdana,arial,sans-serif; font-size: 12px; line-height: 20px;">Добрый день!</p><p style="margin: 1em 0px; padding: 0px; font-family: verdana,arial,sans-serif; font-size: 12px; line-height: 20px;">Приглашаю всех принять участие в соревновании, завершающем серию <a href="http://codeforces.me/zksh">заочных олимпиад ЗКШ</a> для школьников и одновременно являющемся очередным Codeforces-раундом. Начало соревнования - 12 декабря, в 11:00 по московскому времени.&nbsp;</p><p style="margin: 1em 0px; padding: 0px; font-family: verdana,arial,sans-serif; font-size: 12px; line-height: 20px;">Соревнование пройдет по правилам ACM-ICPC, продолжительность контеста - 3 часа.</p><p style="margin: 1em 0px; padding: 0px; font-family: verdana,arial,sans-serif; font-size: 12px; line-height: 20px;">Как и предыдущие школьные индивидуальные олимпиады, соревнование будет рейтинговым для всех участников (и для школьников, и для остальных). Рейтинг будет вычисля...

Full text and comments »

Челлендж::подготовься к респе! Привет, Code<font style="color:#000000">forces</font>! Меньше двух месяцев осталось до респы! Поэтому надо провести это время максимально эффективно! Сегодня придумал такую идею для контроля подготовки к заключительному этапу республиканской олимпиады: буду каждое воскресенье делать запись в блог, подводя итоги недели. Записи буду описывать так: **1) Cамые интересные решённые таски недели, которые буду подразделять на четыре типа:** - <font style="color:#006400"> Решил задачу сам</font> - <font style="color:#FFA500"> Решил с разбором</font> - <font style="color:#FF4500"> Смотрел коды, чтобы понять решение </font> - <font style="color:#8B0000"> Не смог решить (Не решал) </font> Задачи 3 и 4 типа буду стараться перерешивать, и тогда их цвет будет меняться. **2) Олимпиады и раунды, которые решал за неделю.** **3) В целом краткое описание недели, что было интересного.** Что я примерно планирую решать? Далее здесь появятся ссылки на новые блоги: [<font st...

Full text and comments »

Школьная индивидуальная олимпиада #2 (ЗКШ 2010/11) - Codeforces Beta Round #43 (ACM-ICPC Rules) <p> Всем доброго времени суток. </p> <p> Завтра, 5 декабря, в 11:00 по московскому времени я приглашаю всех желающих принять участие в очередном соревновании Codeforces. Оно будет одновременно являться очередной индивидуальной олимпиадой в рамках ЗКШ (подробности <a href="http://codeforces.me/blog/entry/753">тут</a>) и обычным раундом Codeforces для тех, кто не участвует в зачете ЗКШ. </p><p>Это соревнование, как и все предыдущие олимпиады ЗКШ, проводится при поддержке компаний&nbsp;<span class="Apple-style-span" style="font-family: verdana,arial,sans-serif; font-size: 12px; line-height: 20px;"><a href="http://yandex.ru/" style="color: rgb(0, 0, 204);">Яндекс</a></span><span class="Apple-style-span" style="font-family: verdana,arial,sans-serif; font-size: 12px; line-height: 20px;">&nbsp;</span><span class="Apple-style-span" style="font-family: verdana,arial,sans-serif; font-size: 12px; line-height: 20px;">и</span><span class="Apple-style-span" style="font-family: verdana,arial,...

Full text and comments »

Школьная командная олимпиада #1 (ЗКШ 2010/11) Добрый день всем!<div><br></div><div>Приглашаем всех на Школьную командную олимпиаду #1, которая состоится 24 октября в 11:00 MSK. Соревнование будет официальным для <i>команд школьников</i>, как часть серии школьных заочных олимпиад ЗКШ (<a href="http://codeforces.me/blog/entry/753">http://codeforces.me/blog/entry/753</a>), и неофициальным (и не рейтинговым!) для всех остальных.</div><div><br></div><div>Чтобы принять участие официально, каждый участник <i>школьной команды</i> должен сначала <a href="http://codeforces.me/confirm">зарегистрироваться лично</a>, затем из&nbsp;зарегистрированных&nbsp;участников нужно&nbsp;<a href="http://codeforces.me/blog/entry/779">создать команду</a>&nbsp;и, когда будет открыта <a href="http://codeforces.me/contests">регистрация на соревнование</a>, зарегистрировать команду еще и там.</div><div><br></div><div>Надеюсь, что задачи окажутся интересными для школьников с разным уровнем подготовки в программировании, и не только для школьников! Обратите внима...

Full text and comments »

Разбор CodeForces Round 289 (Div.2) (Второй отборочный тур ЗКШ 2015) [problem:509A] В этой задаче нужно было сделать то, что написано в условии: построить таблицу(двумерный массив) по указанным правилам и найти максимум в таблице. Можно было заметить также, что максимальный элемент находится в правом нижнем углу. Также проходило и просто решение рекурсией: ~~~~~ def elem(row, col): if row == 1 or col == 1: return 1 return elem(row - 1, col) + elem(row, col - 1) ~~~~~ Кроме того, можно было заметить в таблице [Треугольник Паскаля](http://ru.wikipedia.org/wiki/Треугольник_Паскаля) и понять, что ответ &mdash; это $\binom{2n - 2}{ n - 1}$ Готовил: [user:AlexDmitriev,2015-01-31] Разбор от: [user:AlexDmitriev,2015-01-31] [problem:509B] Пусть найдутся две кучки, в которых количество камней отличается строго больше чем на $k$, тогда решения не существует: $a_i = \sum_{c=1}^k b_{i, c} \le \sum_{c=1}^k (b_{j, c} + 1) = a_j + k $ Пусть теперь $M = \max a_i \le \min a_i + k = m + k$, покажем, как построить прави...

Full text and comments »

Codeforces Round #289 (Div. 2) + отборочный раунд на ЗКШ Привет, Codeforces! [31 января в 15:00 MSK](http://www.timeanddate.com/worldclock/fixedtime.html?iso=20150131T15&p1=166) состоится раунд #289 для участников из второго дивизиона. Традиционно, участники из первого дивизиона могут участвовать в соревновании вне конкурса. Этот раунд отличается от остальных тем, что он будет проведен по правилам АСМ, то есть результаты проверки на всех тестах вы получаете в режиме онлайн, а его продолжительность составит 3 часа. Данные отличия в правилах вызваны тем, что **этот раунд является вторым отборочным раундом в [ЗКШ](http://codeforces.me/blog/entry/15739)**. Официальный сайт школы &mdash; [http://it-edu.mipt.ru/zksh2015](http://it-edu.mipt.ru/zksh2015). [Там же](http://it-edu.mipt.ru/sites/default/files/rules_otbor.pdf) вы можете найти правила отбора на ЗКШ. Алгоритм действий для школьника, желающего поучаствовать в отборе на ЗКШ (вне зависимости от дивизиона): 1. Зарегистрироваться на школу по ссылке [http://goo.gl/kz2qSf](http://...

Full text and comments »

Обзор решений задачи KQUERY _За последнее время у меня набралось определённое количество заметок на различные темы, с которыми до конца не ясно что делать. Скорее всего, для синих эта информация не слишком актуальна, для красных &mdash; давно очевидна. Из этих заметок вряд ли получится сделать статьи, а достаточно заинтересованный человек вполне может собрать всю приведённую в них информацию из интернета по частям самостоятельно. Тем не менее, я всё же решил сделать пост (или, может быть несколько) на Codeforces, в надежде, что эти сведения для кого-нибудь окажутся полезными._ Оригинальная задача [KQUERY](http://www.spoj.com/problems/KQUERY/) формулируется следующим образом. Дан массив $\relax a$ размера $\relax N \le 3 \cdot 10^4$, а также $\relax Q \le 2 \cdot 10^5$ запросов вида $\relax (l, r, k)$ &mdash; определить количество элементов, больших $\relax k$, на отрезке $\relax [l; r]$. Сразу следует заметить, что из-за достаточно малого TL вердикт Accepted по оригинальной задаче получает только одно из пр...

Full text and comments »

Зимняя компьютерная школа 2016  **Внимание! В связи с переносом дат проведения Открытой олимпиады на 7-8 марта, даты проведения ЗКШ перенесены на один день вперёд!** **Update:** в связи с техническими проблемами англоязычные участники не смогли принять участие в четвертом отборочном туре, поэтому оргкомитетом принято решение провести ещё один отборочный тур 14 февраля в 15:00 по московскому времени. К участию в этом туре приглашаем всех, но будут рассматриваться результаты преимущественно иностранных участников. **С 25 февраля по 5 марта** 2016 года в г. Долгопрудном (Московская область) на базе московского Физтеха пройдет седьмая **Зимняя компьютерная школа (ЗКШ-2016)** для школьников 9-11 классов. **В программе ЗКШ-2016:** - Ежедневные учебные контесты: подготовка к финалу Открытой олимпиады, финалам национальных олимпиад по программированию. - Олимпиады по информатике и программированию, ...

Full text and comments »

Открытая олимпиада по программированию НИТУ «МИСИС», МФТИ и COGNITIVE TECHNOLOGIES 2017 **27 ноября 2016 в 12:00** состоится заочный тур Открытой олимпиады по программированию Национального Исследовательского Технологического Университета «МИСиС», МФТИ и Cognitive Technologies. В этом году олимпиада впервые вошла во всероссийский перечень олимпиад школьников и является олимпиадой второго уровня. Призеры и победители данной олимпиады получают возможность поступить без экзаменов в НИТУ «МИСиС», а также в ряд других ВУЗов. Олимпиада проводится совместно с МФТИ. Заочный тур олимпиады будет оцениваться по правилам ACM ICPC. Все участники пишут индивидуально. Длительность тура 5 часов. К участию приглашаются **школьники 7-11 классов**. Лучшие участники будут приглашены в Москву на очный тур олимпиады, который состоится **15 января 2017 года**. Очный тур будет проводиться на 2 двух площадках: НИТУ «МИСиС» и МФТИ. Организаторы берут на себя расходы, связанные с проживанием иногородних участников (общежития при университетах). Победителям очного тура будут вручены ценные при...

Full text and comments »

Новости Факультета Компьютерных Наук ВШЭ В этом году первый набор [Факультета Компьютерных Наук](http://bit.ly/25msmZi) заканчивает второй курс, и на этом фундамент, обязательный для всех, почти заканчивается. Что же ждет их дальше, на 3-4 курсе и в магистратуре? Ниже я расскажу об этом, а также об основных новостях [ФКН](http://bit.ly/25msmZi): старт специализаций, новая магистерская программа, открытие двух лабораторий, изменения в базовой программе 1-2 курса по итогам первых двух лет существования [ФКН](http://bit.ly/25msmZi), включая оценки и фидбэк от самих студентов. **UPD.** Льготы по олимпиадам опубликованы [здесь](https://ba.hse.ru/data/2016/06/01/1130397875/Москва.pdf), а про всероссийские олимпиады написано [здесь](https://ba.hse.ru/olimp2016). На 3-4 курс все студенты выбирают себе специализацию. Это набор курсов в рамках одной широкой темы, некоторые из которых обязательны для всех, кто выбрал специализацию, а из остальных нужно выбрать определенное количество (не все). Всего у нас будет пять специализаций,...

Full text and comments »

Третий отборочный тур ЗКШ-2017!  А тем временем в это воскресенье состоится уже **третий отборочный тур** на Зимнюю компьютерную школу. Он пройдет 18 декабря в 15:30 по московскому времени. Чтобы получить логин-пароль и ссылку на тур, нужно [зарегистрироваться](https://docs.google.com/a/phystech.edu/forms/d/e/1FAIpQLSfAn8nqPglKv-vpmFntTgCgAmz4EJWEdMvzsepthBUsMeRX6Q/viewform). Рассылка осуществляется в несколько этапов за сутки и за несколько часов до начала тура. Если вам уже высылался логин-пароль перед предыдущими турами, повторно регистрироваться не нужно. Зимняя компьютерная школа в этом году пройдет в МФТИ **с 27 февраля по 8 марта 2017 года.** **В программе ЗКШ-2017:** - Ежедневные учебные контесты: подготовка к финалу Открытой олимпиады, финалу Технокубка, финалам национальных олимпиад по программированию; - Тематические учебные лекции, причём в этом году каждый участник может состави...

Full text and comments »

Второй отборочный тур ЗКШ 2018!  Участники Moscow International Workshop ACM ICPC уже неделю решают контесты, ну а мы тем временем продолжаем готовиться к Зимней Компьютерной Школе 2018. Ведь уже **26 ноября в 12:00** по московскому времени пройдет **второй отборочный тур**. Чтобы получить логин-пароль и ссылку на тур, нужно [зарегистрироваться](https://it-edu.mipt.ru/el/login/index.php). Логин и пароль для доступа к отборочному туру будут доступны в личном кабинете после регистрации. Зимняя компьютерная школа в этом году пройдет в МФТИ **с 26 февраля по 7 марта 2018 года**. В программе ЗКШ-2018: - Ежедневные учебные контесты: подготовка к финалу Открытой олимпиады, финалу Технокубка, финалам национальных олимпиад по программированию; - Тематические учебные лекции, причём в этом году каждый участник может составить свою программу лекций из набора; - Лекции сотрудников базовых организаци...

Full text and comments »

Школьная командная олимпиада #2 (ЗКШ 2010/11): разбор задач A-E, H, J <div><b>Задача A</b></div><div><br></div><div>Один из возможных путей решения задачи - сравнивать каждый листик с уже взятыми. Если он совпал с одним из них, тогда его не нужно брать. Поскольку порядок листьев неважен, можно просто отсортировать их (например, как пары строк) и удалить одинаковые листья.</div><div><br></div><div><b>Задача B</b></div><div><br></div><div>Задача заключается в нахождении количества троек (x, y, z), таких что 0 &lt;= x &lt;= a, 0 &lt;= y &lt;= b, 0 &lt;= z &lt;= c и 0.5 * x + y + 2 * z = n. Перебор всех троек работает долго, однако все возможные значения x и y, удовлетворяющие неравенствам 0 &lt;= x &lt;= a, 0 &lt;= y &lt;= b перебрать можно. Когда x и y фиксированы, значение z определяется однозначно. Получаем решение за O(a*b).</div><div><br></div><div><b>Задача C</b></div><div><br></div><div>Самое простое решение - перебрать все дни с 1 до n и для каждого дня проверить, что он покрывается ровно одним отрезком $[a_i, b_i]$. Если обнаружен день, который пок...

Full text and comments »

Первый отборочный тур ЗКШ 2017!  В Москве на этой неделе пошёл первый снег, мы сразу же подумали про ЗКШ и решили провести **первый отбор** на Зимнюю компьютерную школу, не дожидаясь декабрьско-январской суматохи. Он пройдет через сутки, в воскресенье 30 октября в 12:00 по московскому времени. Чтобы получить логин-пароль и ссылку на тур, нужно [зарегистрироваться](https://docs.google.com/a/phystech.edu/forms/d/e/1FAIpQLSfAn8nqPglKv-vpmFntTgCgAmz4EJWEdMvzsepthBUsMeRX6Q/viewform). Зимняя компьютерная школа в этом году пройдет в МФТИ **с 27 февраля по 8 марта 2017 года.** **В программе ЗКШ-2017:** - Ежедневные учебные контесты: подготовка к финалу Открытой олимпиады, финалу Технокубка, финалам национальных олимпиад по программированию; - Тематические учебные лекции, причём в этом году каждый участник может составить свою программу лекций из набора; - Лекции сотрудников базовых организаций ФИВ...

Full text and comments »

Лауреаты медали Кормена 2010 <img src="http://assets.codeforces.com/images/medals.gif" style="float:left;margin:0.5em 1em;width:200px;"> <p> Закончился 2010 год, и, конечно, все уже готовы не только встретить Старый Новый Год, но и узнать имена тех, кто награжден медалями Кормена за 2010 г. </p> <img src="http://assets.codeforces.com/images/tourist.jpg" style="float:right;margin:0.5em 1.5em;width:140px;"> <p> Итак, в номинации "Лучший участник-школьник 2010" награжден ... барабанная дробь ... <a href="http://codeforces.me/profile/tourist">Геннадий Короткевич</a>. Приняв участие в 5-ти из 6-ти олимпиад ЗКШ, проводимых проектом Codeforces, Геннадий одержал&nbsp;победу&nbsp;в каждом из них! В командном зачете он принимал участие индивидуально, но это не помешало ему обойти всех претендентов на победу.</p> <p> В номинации "Лучший участник 2010" медаль Кормена достается ... <a href="http://codeforces.me/profile/tourist">Геннадию Короткевичу</a>! За прошедший год Геннадий принял участие в 15-ти раундах Co...

Full text and comments »

Школьные заочные олимпиады ЗКШ <img src="http://assets.codeforces.com/images/medals.jpg" style="float:left;margin: 0 1em;"> <p> Добрый день. </p> <p> На базе проекта Codeforces в рамках Зимней компьютерной школы, проводимой <a href="http://mipt.ru/">Московским физико-техническим институтом</a>,&nbsp;состоится серия заочных командных и личных олимпиад по информатике и программированию. Школа проводится при поддержке компаний <a href="http://yandex.ru">Яндекс</a> и <a href="http://abbyy.ru">ABBYY</a>. </p> <p> Вашему вниманию будут предложены три командных и три индивидуальных олимпиады. К участию приглашаются <i>школьники</i> РФ и других стран. </p> <p> Жюри уже активно работает над подготовкой - все олимпиады будут включать в себя задачи широкого спектра сложности и будут интересны и полезны как начинающим, так и опытным участникам. </p> <p> Победителей ждут дипломы и призы! </p> <p> Первая олимпиада будет командная и состоится она 24-го октября в 11:00. Продолжительность олимпиады 5 ч...

Full text and comments »

Школьная командная олимпиада #1 (ЗКШ 2010/11): разбор задачи К Предположим, что верхняя и нижняя стороны прямоугольника фиксированы и нам осталось только выбрать левую и правую стороны. Тогда мы за О(К) можем найти список всех прямоугольников, которые попадают в нашу полосу, а так же список всех прямоугольников, у которых только часть попадает в полосу. Тогда мы можем представить это в виде отсортированного набора отрезков [l,r], где l и r - икс координаты левой и правой сторон прямоугольника.<div><br></div><div>Если какие-то отрезки в нашем наборе имеют общую точку - склеим их в один большой отрезок и запомним что теперь в нем на самом деле два отрезка. Таким образом, после того как мы склеили все отрезки, у нас получится какой-то набор отрезков, для каждого из которых известно количество прямоугольников, которые им покрываются (если в нем есть прямоугольник, который не лежит полностью в нашей полосе, то будем считать что такой отрезок содержит бесконечное количество прямоугольников). Теперь мы можем пройти по всем свободным отрезкам (находящимся...

Full text and comments »

Школьная командная олимпиада #1 (ЗКШ 2010/11): разбор задач <div><b>Задача А</b></div><div><br></div><div>Для получения максимального возможного результата нужно просто отсортировать слагаемые&nbsp;в порядке неубывания коэффициентов (коэффициенты учитываются со стоящими перед ними знаками + и -).&nbsp;Не нужно обращать внимание на a++ или ++a! Вопрос заключается в том, почему это правильно.</div><div><br></div><div>Во-первых, рассмотрим выражение, содержащее только a++.&nbsp;Тогда наше утверждение очевидно: выгодно умножать 'a' на маленькие коэффициенты, пока значение 'a' маленькое, и на большие коэффициенты, когда оно становится больше.&nbsp;То же самое происходит в случае трицательных значений коэффициентов или 'a'.&nbsp;Конечно, это не строгое доказательство. Я надеюсь, что вы еще подумаете над ним,&nbsp;если пока не поняли.</div><div><br></div><div>Во-вторых, рассмотрим выражение k*a+++k*++a, где k - некотрый коэффициент,&nbsp;одинаковый для обоих слагаемых. Пусть начальное значение 'a' равно $a_0$.&nbsp;Вычисляя значение выражения обоими с...

Full text and comments »

Школьная командная олимпиада #2 (ЗКШ 2010/11): разбор задач F, G и I <p> <b>Задача I. Игрушки.</b> </p> <p> В задаче необходимо вывести все возможные разбиения заданного множества на подмножества в порядке, напоминающем код Грея. Перейдем к заданию разбиений с помощью так называемых ограниченно растущих строк. Строка $a_{1}a_{2}a_{n}$ называется ограниченно растущей, если $a_1=0$ и $a_{j+1} \le 1 + max(a_1,\ldots,a_j)$ для $1 \le j &lt; n$. Ограниченно растущая строка для разбиения строится так: $a_i=a_j$ тогда и только тогда, когда элементы $i$ и $j$ принадлежат одному подмножеству в этом разбиении. Например, ограниченно растущая строка для разбиения {1,3},{2},{4} есть 0102. </p> <p> Теперь научимся перебирать все ограниченно растущие строки, каждый раз изменяя одно значение в текущей строке для перехода к следующей. Очевидно, что применительно к разбиениям это будет означать именно то, что требуется в задаче. Достаточно простой способ построения такого списка ограниченно растущих строк называется схемой Эрлиха. Пусть имеется спи...

Full text and comments »

Школьная индивидуальная олимпиада #3 (ЗКШ 2010/11) - Codeforces Beta Round #45 (ACM-ICPC Rules): разбор задач <b>Задачи A и B</b> не представляли идейной сложности, поэтому начнем сразу с C.<br><br><b>Задача C</b><br><br>Положим $\beta = \alpha / 10$. Тогда заданные числа - это $a_1 = [\beta]$, $a_2 = [2 \beta]$, $a_3 = [3 \beta]$, ... $a_n = [n \beta]$ и нужно определить $[(n + 1) \beta]$ ([x] - целая часть числа). Данные равенства эквивалентны системе неравеств: $a_n \le n \beta &lt; a_n + 1$, $n = \overline{1, n}$. Выбирая максимум по левым частям и минимум по правым, получим неравество вида $A \le n &lt; B$. Теперь осталось сравнить целую часть числа $A / (n + 1)$ и $B / (n + 1)$. В случае если B поделилось нацело, нужно вычесть из правой части единичку, т.к. справа неравенство строгое.<br><br><b>Задача D</b><br><br>Создадим векторы $v_i$, в первый из которых $v_1$ будем складывать позиции единичек, в $v_2$ - двоек, в $v_3$ - троек, и т.д. Их можно заполнить за один проход по данной последовательности. Количество перестановок - это количество единичек, или размер первого вектора. Мысленно ...

Full text and comments »

Зимняя Компьютерная Школа 2013 при МФТИ  С 25 февраля по 4 марта 2013 года в г. Долгопрудном (Московская область) на базе московского Физтеха при поддержке компаний Яндекс, ABBYY и 1С пройдет четвертая **Зимняя компьютерная школа (ЗКШ-2013)** для школьников. **В программе ЗКШ-2013:** Ежедневные учебные контесты: подготовка к финалу Открытой олимпиады. Олимпиады по информатике и программированию, математике. Лекции сотрудников Яндекса, ABBYY, 1С о реальных задачах в IT-индустрии. Лекции профессиональных ученых по комбинаторной математике. Спортивные и интеллектуальные игры. **Как попасть в школу:** 1. Зарегистрироваться на сайте http://it-edu.mipt.ru/zksh. (Регистрация продлена до 4 февраля!) 2. Участвовать в отборочных интернет-турах к ЗКШ. **Стоимость участия** в школе: 8000 рублей. **Бесплатное участие** гарантируется победителям и призерам заключительного этапа Всероссийской олимпиады школьников по информатике или математик...

Full text and comments »

Медаль Кормена <img src="http://assets.codeforces.com/images/cormen-ru.jpg" style="margin:0 1em;float:right;"> <p> Всем добрый день. </p> <p> Рады сообщить вам, что в ночь с 31-го декабря 2010 на 1-ое января 2011 будет не только салют, шампанское, поздравления и подарки, но и будут подведены итоги года на <a href="http://codeforces.me/">Codeforces</a>. Сообщаем, что <a href="http://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D1%80%D0%BC%D0%B5%D0%BD">Томас Кормен</a> дал свое согласие на то, чтобы ежегодная награда носила его имя! Итак, мы рады анонсировать ежегодную награду Codeforces – <b>медаль Кормена</b>! </p> <p> В этом году решено присуждать медаль по трем номинациям: </p> <ul> <li>лучший участник соревнований Codeforces</li> <li>лучший участник-школьник соревнований Codeforces (подводится по <a href="http://codeforces.me/blog/entry/753">серии заочных олимпиад ЗКШ</a>)</li> <li>лучший автор задач</li> </ul> <p> Первая из медалей будет вручена участнику, имеющему максимальный <a hre...

Full text and comments »

Необычные модификации не отрезке Добрый день, сообщество CF. Мне нужна помощь и я обращаюсь к вам за ней. Долгое время я думал, что если знаешь простые модификации на отрезке ( присвоение, прибавление, умножение с выдачей суммы, максимума, НОД, НОК и т.п. ), сжатое дерево отрезков, то проблем с модификациями на отрезке быть не должно. Но я ошибался. Проблема у меня следующая. Как осуществить присвоение, прибавление прогрессии на отрезке с выдачей максимума? Арифметической. Может ещё и сумму можно на отрезке получать после этого ( мне кажется, что наврятли ). Может ещё и с геометрической тоже можно ( на грани фантастики да и нигде такого не встречал ). Может можно ещё это делать по остатку от деления на 10^9+7 ( к примеру ) ( мне кажется, что я совсем обкурился пивом). Надеюсь, что это всё не требует персистентность или 2-3 мерные деревья. Вот задачи, которие можно решить этим методом, если он существует конечно. http://codeforces.me/problemset/problem/396/C – HLD ( корневая декомпозиция предложаная ЗКШ у меня н...

Full text and comments »

Школьная индивидуальная олимпиада #2 (ЗКШ 2010/11) - Codeforces Beta Round #43 (ACM-ICPC Rules). Разбор задач B, D, E. <p> <b>Задача B</b>. Футболки от спонсора. </p> <p> Пронумеруем размеры футболок целыми числами от 0 до 4. Для каждого размера будем хранить количество оставшихся футболок этого размера. При обработке очередного участника мы сначала определяем номер его размера, затем одним циклом перебираем размеры футболок и из тех размеров, футболки которых еще остались, выбираем самый подходящий (т.е. с ближайшим номером). </p> <p> <b>Задача D</b>. Парковка. </p> <p> Будем хранить множество машин, которое в данный момент находится на парковке. То, как мы его будем хранить, в данной задаче не принципиально. Для каждой машины, которая в данный момент находится на парковке, будем хранить ее длину и занимаемую ей позицию. При обработке запроса типа 2 нам надо найти машину, которая должна покинуть парковку, и удалить ее из множества. Для этого мы должны нумеровать машины и по номеру запроса понимать, к какой машине он относился. Теперь рассмотрим запрос типа 1. Поскольку водите...

Full text and comments »

Несколько вопросов про паросочетания и не только 1. Задача: даны два множества точек на плоскости (оба размером N), нужно найти совершенное паросочетание с минимальным весом самого тяжелого ребра в нем (вес ребра --- очевидно, Евклидово расстояние). Я умею решать Куном с бинпоиском по весу самого тяжелого ребра за $O(N^3\,logN)$. Вопрос: как решить эту задачу за чистый куб путем добавления в алгоритм какой-то жадности? Хопкрофта-Карпа и Диница прошу не предлагать. **Ответ: [вот так](http://codeforces.me/blog/entry/4676#comment-95373).** 2. Задача о поиске совершенного паросочетания в регулярном двудольном графе объяснялась в харьковской ЗКШ в этом году, но только для тех графов, в которых степени каждой вершины являются степенями двойки. Вопрос: как решать эту задачу для графов с произвольными степенями вершин? Применение алгоритма Хопкрофта-Карпа очевидно, но мне кажется, что существует что-то побыстрее. 3. Задача: дан регулярный граф, нужно найти в нем гамильтонов цикл. Вопрос: существует ли алгоритм, который гарантированно н...

Full text and comments »

Школьная индивидуальная олимпиада #2 (ЗКШ 2010/11) - Codeforces Beta Round #43 (ACM-ICPC Rules): разбор задач A, C, F и G <div><b><span class="Apple-style-span" style="font-weight: normal; "><b>Задача A</b></span><br></b></div><div><b><span class="Apple-style-span" style="font-weight: normal; "><b><br></b></span></b></div><div>Задача решается простым моделированием описанного процесса. Главное - правильно обработать переход через n. Это можно сделать либо взятием номеров по модулю n (с прибавлением 1), либо вычитать n каждый раз, как текущий номер стал больше n.</div><div><br></div><div><b>Задача C</b></div><div><br></div><div>Сначала посчитаем, сколько в последовательности хомячков. &nbsp;Пусть их h. Переберем позицию, в которой будет начинаться последовательность хомячков, и для каждой начальной позиции посчитаем, сколько тигров оказалось в отрезке h, начиная с этой позиции. &nbsp;Этих тигров придется поменять с хомячками за количество обменов, равное количеству тигров, стоящих не на своем месте. Выберем минимум по всем начальным позициям.</div><div><b><span class="Apple-style-span" style="font-weight: ...

Full text and comments »

Школьная командная олимпиада #2 (ЗКШ 2010/11) <div>Всем добрый день!</div><div><br></div>Я рада пригласить вас принять участие в следующем раунде серии <a href="http://codeforces.me/blog/entry/753">зимних школьных олимпиад по информатике</a>, который состоится 6 ноября в 14:00 MSK.&nbsp;<div><br></div><div>Соревнование будет официальным для команд школьников и неофициальным и нерейтинговым для всех остальных. Напоминаю, что если у вас школьная команда, то вы должны <a href="http://codeforces.me/blog/entry/753">зарегистрировать</a> всех участников для участия в серии, если вы еще этого не сделали.<br><div><br></div><div>Продолжительность соревнования 5 часов, правила - стандартные для ACM ICPC.&nbsp;</div><div><br></div><div>В подготовке задач участвовали я, Дмитрий Матов, Полина Бондаренко, Михаил Мирзаянов, а также Мария Белова, которая перевела их на английский. Мы все надеемся, что вам будет интересно поучаствовать в соревновании.</div><div><br></div><div>Удачи! &nbsp;</div></div><div><br></div><div><b>UPD. Условия в PDF: <a hr...

Full text and comments »

Анонс пятой Зимней Компьютерной Школы  Физтех объявляет о проведении пятой **Зимней компьютерной школы (ЗКШ-2014)**, которая состоится **26 февраля по 6 марта 2014 г.** на базе МФТИ в Долгопрудном. Для участия в ЗКШ школьнику необходимо заполнить форму регистрации и пройти отборочные интернет-туры, проводящиеся **12, 19 января 2014г. в 10:00 мск, 25 января 2014г. в 15:00 мск** (засчитывается максимальный результат по одному из туров). [cut] <br> **В программе ЗКШ-2014:** - Ежедневные учебные контесты: подготовка к финалу Открытой олимпиады. - Олимпиады по информатике и программированию, математике. - Лекции сотрудников базовых организаций факультета инноваций и высоких технологий о реальных задачах в IT-индустрии. - Лекции профессиональных ученых по комбинаторной математике. - Спортивные и интеллектуальные игры. **Бесплатное участие, не требующее прохождения отборочных интернет-туров,** гарантируется победителям и...

Full text and comments »

Интерфейс создания команд <p>Всем добрый день.</p><p>Теперь вы можете создавать команды и приглашать в них других пользователей Codeforces. Напоминаю, что первая заочная олимпиада ЗКШ будет командная, и для официального участия в ней будут допущены только команды (все участники которой <a href="http://codeforces.me/confirm">зарегистрированы для участия</a> в серии заочных олимпиад).</p><p>P.S. Заметим, что пока это только первая версия интерфейса системы вокруг команд. Мы планируем его расширить, предложения приветствуются :)</p><p>MikeMirzayanov</p>

Full text and comments »

ЗКШ отборочный тур и CodeForces #386 раунд Привет CodeForces! С прошедшим всех #385 раундом и с наступающим #386 =) Это такое удовольствие писать раунды CodeForces и такая волнительная интрига после окончания контеста ждать конечных результатов и чувство соперничества между участниками, очень незабываемо... Иногда бывает ностальгия по любимым CF раундам, когда их часто не бывает. Но сейчас у меня очень тяжелый выбор между отборочным туром в ЗКШ и #386 раундом, так хочется успеть и там и тут. Но расписание убивает у меня эту возможность :( Прошу вас всех помочь решить эту проблему, что бы каждый любил то что любит и добивался чего он хочет. Я думаю вместе мы справимся)  Большое спасибо за внимание!!!

Full text and comments »

ЗКШ: Второй отбор Всем доброго времени суток. [17 января в 15:00 мск](http://www.timeanddate.com/worldclock/fixedtime.html?day=17&month=1&year=2016&hour=15&min=0&sec=0&p1=166) пройдет второй отборочный этап Зимней школы по программированию. Более подробно о школе можно почитать на официальном [сайте](http://it-edu.mipt.ru/zksh2016).  Предлагаю обсудить задачи после окончания контеста. **UPD:** Контест завершен!

Full text and comments »

Специальный отборочный тур в ЗКШ-2014! Внимание! Объявляется о проведении специального отборочного тура в ЗКШ-2014! Тур состоится <b> 9 февраля 2014г</b>. <b>Начало тура в 10:00 по московскому времени</b>, длительность тура <b> 3 часа </b>. Ссылка на регистрацию и сам тур появится апдейтом этой новости не позднее, чем за 2 часа до начала тура. [cut] <br> Все подробности и обновления публикуются в разделе <a href="http://it-edu.mipt.ru/ru/zksh2014">ЗКШ-2014</a>.

Full text and comments »

Регистрация на первый отборочный тур ЗКШ-2014! Началась регистрация на первый отборочный тур ЗКШ-2014! Для прохождения регистрации пройдите по <b><a href="http://93.175.29.133/cgi-bin/new-register?contest_id=37&locale_id=1">этой ссылке</a></b> Напоминаем, что <b>начало тура в 10:00 по московскому времени</b>, длительность тура <b> 3 часа </b>. [cut] <br> Все подробности и обновления публикуются в разделе <a href="http://it-edu.mipt.ru/ru/zksh2014">ЗКШ-2014</a>.

Full text and comments »

Регистрация на второй отборочный тур ЗКШ-2014! Началась регистрация на второй отборочный тур ЗКШ-2014! Для прохождения регистрации пройдите по <b><a href="http://93.175.29.133/cgi-bin/new-client?contest_id=38">этой ссылке</a></b> Напоминаем, что <b>начало тура в 10:00 по московскому времени</b>, длительность тура <b> 3 часа </b>. [cut] <br> Все подробности и обновления публикуются в разделе <a href="http://it-edu.mipt.ru/ru/zksh2014">ЗКШ-2014</a>.

Full text and comments »

Началась регистрация на третий отборочный тур ЗКШ-2014! Началась регистрация на третий отборочный тур ЗКШ-2014! Для прохождения регистрации пройдите по <b><a href="http://93.175.29.133/cgi-bin/new-client?contest_id=39">этой ссылке</a></b> Напоминаем, что <b>начало тура в 15:00 по московскому времени</b>, длительность тура <b> 3 часа </b>. [cut] <br> Все подробности и обновления публикуются в разделе <a href="http://it-edu.mipt.ru/ru/zksh2014">ЗКШ-2014</a>.

Full text and comments »

Третий отборочный тур в ЗКШ-2012 Всем привет! Мы рады сообщить, что **12 февраля** пройдет третий (заключительный) отборочный тур в [ЗКШ-2012](http://fivt.fizteh.ru/zksh/2012/). Как и всегда мы приглашаем принять участие в нем всех заинтересованных. </p>Время начала тура: <b>12:00 (мск)</b>. Продолжительность: 3 часа.<br /><a href="http://fivt.fizteh.ru/zksh/2012/rounds/a_5cu4i9.html">Правила тура</a><br /><a href="http://93.175.29.133/cgi-bin/new-register?contest_id=7&locale_id=1">Регистрация на тур</a><br /> Удачи! И ждем вас на ЗКШ.

Full text and comments »

Частота контестов <P>Толчком к написанию этого сообщения послужил <A href="http://codeforces.me/blog/entry/856">пост</A> пользователя gasya о сайте CodeChef.com. Последнее время стал замечать, что становится все больше сайтов, где проводятся регулярные контесты. Вследствие этого начинают перекрываться времена контестов. </P><P>Например, в субботу будет:</P><UL><LI>Школьная командная олимпиада #3 (ЗКШ 201011) в 14:00</LI><LI>Тренировка ИТМО в 16:30</LI><LI>487-й Single Round Match на ТС в 20:00</LI></UL><P>Назрели следующие вопросы:</P><P>Такое было всегда и я это заметил только сейчас (: или же такая тенденция действительно существует?</P><P>Контесты на каких сайтах Вы предпочитаете? Какие решаете регулярно, какие "как получится", а какими пренебрегаете?</P>

Full text and comments »

ЗКШ: Третий отбор Вчера завершился третий отборочный интернет-тур в ЗКШ. Было бы интересно, я думаю, обсудить задачи. В частности, очень интересно, как решать вторую задачу.

Full text and comments »

ЗКШ: Первый отбор Всем доброго времени суток. Сегодня прошел первый отборочный этап Зимней школы по программированию. Более подробно о школе можно почитать на официальном [сайте](http://it-edu.mipt.ru/zksh2016).  Предлагаю обсудить задачи здесь.

Full text and comments »

Куда ехать летом? Наверняка некоторые школьники и студенты пользующиеся Codeforces посещали ЛКШ, Фоксфорд, ЛШП, ЗКШ и другие подобные места. Так вот, хотелось &mdash; бы узнать, куда ещё можно поехать летом для обучения спортивному программированию? Возможно есть хорошие варианты в Белорусии и Китае с преподаванием на русском или английском? Я был &mdash; бы рад услышать мнение людей которые бывали в местах куда они советуют поступать. Заранее спасибо

Full text and comments »