Начало финала в 12.00 по московскому времени. В зале не было интернета, поэтому делаю эту запись с опозданием.

Вот некоторые ссылки, по которым можно будет что-то узнать о ходе финала:

• официальный сайт, там будет ссылка не результаты и на видеотрансляцию
• альтернативный монитор
• проект snarknews о финале
• блог Петра Митричева о финале

Болейте за наших!

Официальные мероприятия отнимают много времени, поэтому эта запись больше напоминает краткий отчет о прошедших событиях.

На второй день нашего пребывания в польской столице мы отправились совершить пешую прогулку по центру города. Было холодно, ветрено и накрапывал дождик, поэтому некоторым членам команды, не взявшим с собой теплой одежды, пришлось прикупить шапок, шарфов и свитеров с польской символикой в сувенирных магазинах. Старый город, не сохранившийся во время Второй Мировой войны, но в точности воссозданный потом, произвел на нас очень приятное впечатление. Знаете, вот когда я пытаюсь представить исторический центр европейского города, воображение рисует именно такую картину: узкие улочки, выложенные брусчаткой, шпили башен с часами, черепичные крыши…

Этой записью я начинаю небольшое повествование о поездке на финал чемпионата мира по программированию в Варшаву делегации Саратовского государственного университета. Состав делегации такой:

• Максим Иванов (e-maxx), Артем Рахов (RAD), Николай Кузнецов (NALP) — команда Saratov SU 2;
• тренер Михаил Мирзаянов с женой Екатериной и дочкой Таней;
• Антонина Гавриловна Федорова и Татьяна Владимировна Семенова — наше руководство;
• ну и я (Nerevar), в качестве второго тренера.

Для команды это вторая и последняя поездка на финал (в прошлом году они привезли из Орландо серебряные медали), а для меня это первая поездка на финал не в статусе участника (участвовал я в 2009 и 2010 годах, тоже успешно).

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

Во вторник, 18 октября, в Саратове состоится X региональная командная олимпиада школьников по программированию. Жюри олимпиады подготовило комплект интересных задач. Мы подумали, что будет неправильно, если эти задачи будут доступны для решения только приехавшим к нам школьникам, поэтому решили провести соревнование на Codeforces на задачах этой олимпиады.

Контест начнется в 10.30 по московскому времени (через полчаса после начала самой олимпиады: это сделано для того, чтобы организаторы могли спокойно ее начать) и будет длиться 5 часов. Соревнование будет проведено по правилам ACM ICPC. Участвовать в нем можно будет как лично, так и командно. Для личных участников контест будет рейтинговым. Регистрация на контест уже идет, и продлится она вплоть до конца соревнования.

В подготовке задач для олимпиады принимали участие члены лучших на этот момент студенческих команд СГУ Геральд Агапов, Полина Бондаренко, Иван Фефер, Артем Рахов, Николай Кузнецов, Эдвард Давтян, Павел Холкин и Игорь Кудряшов, а также ветераны Наталья Бондаренко, Михаил Мирзаянов и я, Дмитрий Матов. Мария Белова также отлично потрудилась и перевела задачи олимпиады на английский язык.

Желаю всем получить удовольствие от решения задач!

Условия задач будут доступны по ссылкам:

• русский вариант
• английский вариант

В задачах будет использован файловый ввод-вывод. Внимательно читайте условия!

Как принято говорить в таких случаях: "Вот и закончилась серия заочных школьных олимпиад ЗКШ 2010/2011!"

Все олимпиады серии проводились при поддержке компаний Yandex и ABBYY. Было проведено 6 соревнований: 3 командных олимпиады и 3 индивидуальных. Самое время подвести итоги и выявить победителей олимпиады. Результаты по двум номинациям (командной и личной) подводились отдельно - в каждой из них для участников брались в расчет результаты двух лучших выступлений из трех. Вот ссылки на суммарные результаты по каждой номинации:

• результаты командных олимпиад
• результаты индивидуальных олимпиад

Всего на серию было зарегистрировано около 750 участников из самых разных стран мира. Конечно, большую часть составили участники из России. Как можно видеть, в командных олимпиадах приняло участие около 180 команд, а в индивидуальных - более 400 школьников.

Задача B. Футболки от спонсора.

Пронумеруем размеры футболок целыми числами от 0 до 4. Для каждого размера будем хранить количество оставшихся футболок этого размера. При обработке очередного участника мы сначала определяем номер его размера, затем одним циклом перебираем размеры футболок и из тех размеров, футболки которых еще остались, выбираем самый подходящий (т.е. с ближайшим номером).

Задача D. Парковка.

Будем хранить множество машин, которое в данный момент находится на парковке. То, как мы его будем хранить, в данной задаче не принципиально. Для каждой машины, которая в данный момент находится на парковке, будем хранить ее длину и занимаемую ей позицию. При обработке запроса типа 2 нам надо найти машину, которая должна покинуть парковку, и удалить ее из множества. Для этого мы должны нумеровать машины и по номеру запроса понимать, к какой машине он относился. Теперь рассмотрим запрос типа 1. Поскольку водитель стремится поставить машину как можно ближе к началу парковки, то мы можем сузить множество рассматриваемых вариантов положений для парковки: включим в это множество начало парковки а также все позиции, которые находятся ровно через b метров после переднего края какой-либо машины. Для каждой из этих позиций мы должны выяснить, можно ли припарковать машину в ней, а затем выбрать самую ближайшую из допустимых позиций.

Задача E. Расческа.

Пусть входная матрица называется a. Посчитаем частичные суммы в каждой строке: . Естественно, все частичные суммы надо посчитать за O(nm). Теперь будем решать задачу динамическим программированием. Пусть d_i, j это наибольшая сумма чисел, которую мы можем взять в первых i строках, не нарушая в них условия "расчески", при этом взяв в i-й строке j чисел. Очевидна инициализация динамики: d_1, j = s_1, j. Теперь определим переходы для i > 1:

1) Если i четно, то .

2) Если i нечетно, то .

Вычисление значений d_i, j непосредственно по этим формулам имеет асимптотику O(nm²). Теперь заметим, что если в случае, когда i четно, перебирать j по убыванию, а если нечетно, то по возрастанию, и вычислять d_i, j в таком порядке, то максимум значений d_{i - 1, k} в предыдущей строке можно не вычислять каждый раз, а считать по ходу. Такое решение будет иметь сложность O(nm) и будет проходить все тесты.

Всем доброго времени суток.

Завтра, 5 декабря, в 11:00 по московскому времени я приглашаю всех желающих принять участие в очередном соревновании Codeforces. Оно будет одновременно являться очередной индивидуальной олимпиадой в рамках ЗКШ (подробности тут) и обычным раундом Codeforces для тех, кто не участвует в зачете ЗКШ.

Это соревнование, как и все предыдущие олимпиады ЗКШ, проводится при поддержке компаний Яндекс и ABBYY.

Совернование пройдет по правилам ACM-ICPC.

Участники, не участвующие в зачете олимпиад ЗКШ, будут отображаться в таблице результатов как участники "вне конкурса". Тем не менее, раунд будет рейтинговым для всех, а рейтинг будет посчитан в соответствии с объединенной таблицей результатов.

Авторы задач соревнования: Наталья Бондаренко и я. Благодарим Эдварда Давтяна за помощь в подготовке контеста, а также Марию Белову за перевод условий задач.

Не забудьте зарегистрироваться для участия в соревновании. Удачи на контесте!

• Русская версия
• Английская версия

UPD: Результаты соревнования. Поздавляем Геннадия Короткевича, победившего в олимпиаде ЗКШ, и Петра Митричева, победителя 43 бета-раунда.

UPD: Ссылки на разборы задач: A,C,F,G и B,D,E.

Задача I. Игрушки.

В задаче необходимо вывести все возможные разбиения заданного множества на подмножества в порядке, напоминающем код Грея. Перейдем к заданию разбиений с помощью так называемых ограниченно растущих строк. Строка a₁a₂a_n называется ограниченно растущей, если a₁ = 0 и a_j + 1 ≤ 1 + max(a₁, ..., a_j) для 1 ≤ j < n. Ограниченно растущая строка для разбиения строится так: a_i = a_j тогда и только тогда, когда элементы i и j принадлежат одному подмножеству в этом разбиении. Например, ограниченно растущая строка для разбиения {1,3},{2},{4} есть 0102.

Теперь научимся перебирать все ограниченно растущие строки, каждый раз изменяя одно значение в текущей строке для перехода к следующей. Очевидно, что применительно к разбиениям это будет означать именно то, что требуется в задаче. Достаточно простой способ построения такого списка ограниченно растущих строк называется схемой Эрлиха. Пусть имеется список ограниченно растущих строк s₁, s₂, ..., s_k длины n - 1, удовлетворяющий требуемому порядку. Получим из него список для n. Пусть s_i = a₁a₂... a_n - 1, а m = 1 + max(a₁, ..., a_n - 1). Тогда, если i нечетно, то будем поочередно приписывать к строке s_i цифры 0, m, m - 1, ..., 1, иначе будем приписывать цифры 1, ..., m - 1, m, 0. В результате каждого приписывания мы получаем очередную строку длины n. Таким образом, начиная со списка 0 для n = 1 мы последовательно получим списки 00, 01 для n = 2 и 000, 001, 011, 012, 010 для n = 3. Схема Эрлиха описана в 3 выпуске 4 тома труда Кнута "Искусство программирования" на страницах 83-84.

Задача G. Тир.

Будем решать немного другую задачу: для каждой мишени определим, какой выстрел ее поражает. Для этого упорядочим все мишени по возрастанию координаты z и будем перебирать их в этом порядке. Мишень обрабатывается следующим образом. Рассмотрим все выстрелы, которые потенциально могут в нее попасть. Очевидно, что это такие выстрелы, координаты которых попадают в прямоугольную область, которая является проекцией мишени на плоскость стрельбы. Среди таких выстрелов мишень поразит тот выстрел, который произошел раньше остальных. После того, как мы нашли этот выстрел, мы исключим его из дальнейшего рассмотрения, и будем дальше перебирать мишени. Легко видеть, что будет выполняться такой инвариант: на момент обработки очередной мишени все выстрелы, которые были направлены в нее, но не долетели по причине попадания в другие мишени, будут уже обработаны.

Теперь о том, как эффективно реализовать описанный алгоритм. Будем хранить выстрелы в некоторой структуре данных. Легко выделить 2 вида запросов к этой структуре:

В качестве такой структуры можно использовать двумерное дерево отрезков с функцией минимума. Не буду вдаваться в то, что представляет из себя эта структура. Некоторую сложность представляет организация удаления элемента. Но ситуация облегчается тем, что присутствуют только лишь операции удаления, а добавлений нет. Поэтому на каждом уровне дерева можно заранее предподсчитать, какой элемент станет следующим минимумом при удалении данного. Общая асимптотика авторского решения составляет O((N + M)log²N.

Задача F. BerPaint.

Представим, что все отрезки проведены. Разобьем прямоугольник для рисования на набор областей таких, что строго внутри каждой области не содержится точек, принадлежащих исходным отрезкам, и набор отрезков, разделяющих эти области. При этом в новый набор отрезков могут входить не только части проведенных отрезков, но и некоторые фиктивные отрезки. Изначально цвет всех областей белый, а отрезки черные либо белые в зависимости от того, фиктивные они иили нет (фиктивные отрезки, которые не являются частью никакого из проведенных отрезков, имеют белый цвет). При этом граница каждой области не считается принадлежащей ей. Построим граф, вершинами которого будут области и полученные отрезки. В этом графе будем проводить ребра в следующих случаях:

Очевидно, что любая область, которая может быть окрашена в результате заливки, соответствует некоторой компоненте связности построенного графа. Поэтому задачу можно решать так. Для каждой вершины будем хранить ее цвет. При обработке операции заливки мы находим все вершины такие, что соответствующие им объекты содержат точку заливки. При этом, если вершине соответствует область, то точка должна находиться строго внутри области. Если вершине соответствует фиктивному отрезку, то точка должна принадлежать этому отрезку, но не совпадать ни с одним из его концов. В случае нефиктивного отрезка точка должна просто принадлежать ему. Из всех найденных вершин запустим обход графа, который обойдет все вершины, достижимые из данной и имеющие с ней одинаковый цвет, и окрасит их в цвет заливки. После проведения всех заливок нужно просто для каждого цвета, в который окрашена хотя бы одна вершина, просуммировать площадь объектов, соответствующих вершинам, окрашенным в этот цвет.

Основную сложность в задаче представляет разбиение на области. В авторском решении это делается методом вертикальной декомпозиции. Разобьем сначала прямоугольник на вертикальные полосы, такие, что строго внутри каждой полосы не находится никакая из концевых точек отрезков или точка пересечения каких-то отрезков. Затем каждую из этих полос разобъем на трапеции отрезками, которые пересекают эту полосу. Добавим нобходимые для отделения трапеций друг от друга фиктивные вертикальные отрезки и построим граф. Не исключаю, что подобный граф областей и отрезков может быть построен и более простым способом.

Всем доброго времени суток.

Сегодня на Codeforces необычный день: сразу два раунда, днем, да еще со столь небольшим перерывом. А объясняется это тем, что сегодня в Саратове проходит IX Региональная командная олимпиада школьников по программированию, и задачи с нее (а они весьма неплохие) решено было дать на раунды Codeforces.

По этой причине авторов у сегодняшних задач много. Не поленюсь перечислить весь состав жюри олимпиады, все члены которого хорошо знакомы вам как авторы задач на Codeforces. Это Артем Рахов, Николай Кузнецов, Наталья Бондаренко, Геральд Агапов,Полина Бондаренко, Иван Фефер, Эдвард Давтян, Игорь Кудряшов, Павел Холкин и я. Все мы отлично потрудились и надеемся, что вы оцените наши задачи.

Отдельное спасибо стоит сказать Марии Беловой и Юлии Сатушиной за перевод задач на английский язык.

Обращаю ваше внимание на то, что сегодня во всех задачах будет файловый ввод-вывод. Однако генератор для взлома, как обычно, должен выводить в stdout.

Желаю всем удачи на контестах!

UPD: Результаты 35-го раунда. Поздравляем победителя, участника с ником Naginchik, с впечатляющим дебютом!

UPD: Результаты 36-го раунда.

Ссылки на разборы задач: A, B, C, D, E.

Дорогие, милые девушки! От лица команды проекта Codeforces хочу поздравить вас с замечательным праздником, с Международным Женским Днём!

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