Привет, Codeforces!

Очередной сезон соревнований по программированию стартовал, и самое время поднять мотивацию многим из вас.

От лица фонда Botan Investment и его президента Виктора Шабурова хочу анонсировать уникальную акцию. Цель акции — поддержать и развить интерес к спортивному программированию в регионах России. Пока Москва и СПб исключены из списка, а студенты и выпускники вузов других городов могут получить приз: 50000 рублей и поездку в Сочи для знакомства с командами стартапов Botan Investment.

Для того, чтобы получить приз, ты должен:

• стать красным (гроссмейстером) на Codeforces и быть им на протяжении трех раундов подряд;
• учиться на 4-м или более курсе университета или быть выпускником вуза РФ;
• быть не старше 30 лет;
• быть готовым приехать в Сочи (разумеется, за наш счет) и очно подтвердить свои навыки на очередном раунде.

Более подробно об акции — на сайте Botan Investment.

Виктор, я думаю, не нуждается в представлении на Codeforces, потому как еще свеж в памяти Looksery Cup 2015.

Если ты уже готов — смело пиши на [email protected] по вопросам организации поездки.

Спешу познакомить вас с авторскими идеями решений задач сегодняшнего раунда. Авторы разбора первых пяти задач — HolkinPV и gridnevvvit, разбор последних двух задач написан мной.

479A - Выражение

В этой задаче нужно было рассмотреть несколько случаев и выбрать лучших ответ. Это можно было сделать так:

int ans = a + b + c;
ans = max(ans, (a + b) * c);
	ans = max(ans, a * (b + c));
	ans = max(ans, a * b * c);

	cout << ans << endl;

479B - Башни

Эта задача решается жадным образом. На каждой итерации нашего алгоритма будем перекладывать кубик с башни с максимальной высотой на башню с минимальной высотой. Для этого можно каждый раз за время O(N) заново находить позиции минимума и максимума в массиве. Итоговое решение тогда будет иметь асимптотику O(KN).

479C - Экзамены, 480A - Экзамены

Эта задача решается жадным образом. Отсортируем все экзамены по неубыванию даты фактической сдачи (то есть по a_i), при равенстве по неубыванию даты досрочной сдачи (то есть b_i). Рассмотрим экзамены в получившемся порядке и будем поддерживать текущий ответ. В первую очередь будем стараться сдать очередной экзамен досрочно (если это не нарушит условие задачи, то есть если никакой предыщий экзамен мы не сдавали позже досрочной даты этого экзамена). В противном случае сдадим этот экзамен в дату его фактической сдачи. Обновим текущим ответ выбранной датой сдачи этого экзамена.

std::sort(a, a + n);  // а - массив пар, где первый элемент фактическая сдача экзамена, а                        второй элемент - досрочная
int best = -1;
for(int i = 0; i < n; i++) {
if (best <= a[i].second) {
		best = a[i].second;
	} else {
	 	best = a[i].first;
	}
}	

479D - Прыжки в длину, 480B - Прыжки в длину

Нетрудно догадаться, что ответом на эту задачу может быть 0, 1 или 2. Если изначально мы можем отмерить расстояния x и y, то сразу выведем 0. Иначе попробуем получить ответ нанесением одной метки. Если это не удастся, в качестве ответа всегда можно вывести две метки, равные x и y соответственно.

Чтобы проверить, можно ли получить ответ 1, переберем каждую из имеющихся отметок, пусть она находится на расстоянии r. Тогда попробуем добавить отметку на одной из позиций: r - x, r + x, r - y, r + y. Если хотя бы в одном из случаев станет возможным отмерить x и y, то можно сразу выводить полученный ответ. Проверить, что можем отмерить x и y, просто. К примеру, пусть мы сделали отметку в r + x (т.е. x мы уже научились отмерять). Тогда надо лишь проверить, что есть отметка в r + x + y или r + x - y, например, бинарным поиском (т.е. отметки отсортированы). Надо также не забыть проверить, что отметки попадают в [0, L].

479E - Катаемся на лифте, 480C - Катаемся на лифте

Эта задача решается при помощи динамического программирования. Состоянием динамики будет пара (i, j), где i — количество посещенных этажей, j — номер этажа, на котором мы сейчас находимся. Начальным состоянием является пара (0, a), конечными состояниями являются пары (k, v), где v — любой этаж от 1 до n.

Чтобы осуществить переход, нужно перебрать следующий посещаемый этаж и пересчитать ответ. Однако нельзя выполнять такой переход в явном виде, поскольку решение будет иметь асимптотику O(N³). Чтобы решение уложилось в требуемый лимит по времени, нужно воспользоваться частичными суммами. При переходе от i к i + 1 предпосчитаем в дополнительном массиве частичные суммы посчитанных ранее динамик (с предыдущей итерации). После этого воспользуемся динамическим программированием “назад” и при подсчете очередного значения будем делать запрос суммы на отрезке в посчитанном массиве частичных сумм. Таким образом, решение будет иметь асимптотику O(N²).

Авторское решение: 8322623

480D - Посылки

Сделаем два наблюдения.

Во-первых, посмотрим на посылки как на отрезки [$in_i, out_i$]. Верно следующее утверждение: если коробка i оказалась в какой-то момент времени сверху коробки j (не обязательно непосредственно сверху), то .

Во-вторых, представим, что на платформе находятся какие-то посылки. Оказывается, что все, что нам нужно знать про этот набор посылок, чтобы понимать, можем ли мы положить что-то сверху, это “остаточная прочность” всех этих посылок. Остаточная прочность определяется так: для каждой посылки из набора остаточная прочность равна прочности этой посылки за вычетом суммарного веса всех стоящих на ней. Для набора посылок остаточная прочность считается как минимум из остаточных прочностей посылок в наборе. Таким образом, новую посылку можно положить, если ее вес не превосходит остаточной прочности уже имеющихся коробок.

Это приводит нас к идее решения задачи динамическим программированием. Пусть в данный момент времени верхняя посылка на платформе имеет номер i, а остаточная прочность имеющихся на платформе коробок равна rs. Сделаем эту пару (i, rs) состоянием динамики: представим, что у нас есть исходная задача, в которой есть только те посылки, которые вкладываются в [in_i, out_i], а платформа имеет прочность rs. В значении динамики d(i, rs) будем хранить ответ для этой новой задачи. Какие существуют переходы? Мы должны выбрать набор посылок i(1), i(2), ... i(k) таких, что

• out_i(j) ≤ in_i(j + 1), т.е. отрезки не пересекаются (кроме концов) и отсортированы по времени;
• вес любой из выбранных посылок не превосходит rs.

Этот выбор соответствует следующей последовательности операций: сначала поставить сверху посылки i посылку i(1). Мы перейдем в состояние i(1), min(rs - w_i(1), s_i(1)), прибавив к сумме стоимость коробки i(1) и ответ для нового состояния. Затем мы снимем все коробки, включая i(1), и поставим i(2), сделаем переход, затем снимем все вплоть до i(2), поставим i(3), и т.д.

Поскольку количество состояний в динамике у нас получилось O(NS), то переходы должны суммарно выполняться за O(N). Этого можно добиться, реализовав внутри несложную вспомогательную динамику. Должно получиться решение со сложностью O(N²S). Отметим, что для единообразия можно считать платформу коробкой номер 0, которая приходит раньше всех, и выходит позже всех. Тогда ответ на задачу — просто значение d(0, S).

480E - Парковка

Будем называть приезды машин на парковку событиями.

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

Авторское решение использует принцип разделяй и властвуй. Давайте напишем рекурсивную функцию, которая принимает подтаблицу, границами которой являются r₁, r₂, c₁, c₂ (r₁ ≤ r₂, c₁ ≤ c₂), а также список всех событий парковки, которые происходят в этой подтаблице. Задача функции — рассмотреть то, как меняются максимальные пустые квадраты в этой таблице по прошествии этих событий, и попытаться обновить ответы для некоторых событий.

Предположим, что c₂ - c₁ ≤ r₂ - r₁ (второй случай будет симметричным). Давайте возьмем среднюю строку подтаблицы: r = (r₁ + r₂) / 2. Разделим все квадраты в подтаблице на три части: те, что строго выше r, те, что строго ниже r, и те, что пересекают r. Для первых двух частей вызовемся рекурсивно (естественно, списки событий при этих вызовах будут свои). Теперь осталось только рассмотреть квадраты, пересекающие (имеющие общие клетки) со строкой r.

По исходной таблице для каждой клетки (r, c) мы можем посчитать расстояние до ближайшей занятой клетки в каждом из четырех направлений (или до края, если такой нет): up(r, c), down(r, c), left(r, c) и right(r, c). Используя эту информацию, мы сейчас построим для строки r две гистограммы: первая представляет из себя массив значений up(r, c) при c₁ ≤ c ≤ c₂, вторая — массив значений down(r, c) при c₁ ≤ c ≤ c₂. Здесь я называю массивы гистограммами, потому что они фактически означают высоты столбиков из пустых клеток, начинающихся в строке r. Назовем первую гистограмуу верхней, а вторую — нижней. Рассмотрим все события, происходящие в подтаблице, в порядке их появления. Каждое событие меняет лишь одно значение в гистограмме. Пусть после мы имеем гистограммы после события с номером x, а следующие событие имеет номер y. Тогда, если мы найдем максимальный пустой квадрат в этих гистограммах (пусть его размер k), то мы сможем обновить ответы для всех событий от x до y - 1 значением k.

Осталось только научиться искать максимальный квадрат в двух гистограммах. Это можно сделать с помощью метода двух указателей. Поставим первый указатель в начало. Будем двигать второй указатель до тех пор, пока в гистограммах есть такой квадрат: квадрат со стороной k имеется, если (минимум на отрезке в первой гистограмме) + (минимум на отрезке во второй гистограмме) — 1 >= k. После того, как это свойство нарушилось, двигаем первый указатель. Для того, чтобы находить минимум за O(1), авторское решение для каждой гистограммы заводит очередь с поддержкой минимума за O(1). Таким образом, поиск максимального квадрата осуществляется за линейное время.

Давайте попробуем оценить время работы. Количество действий внутри одного вызова (без учета рекурсивных вызовов в половинах) равно len·q, где len — длина наименьшей из сторон подтаблицы, а q — количество событий в ней. Если мы представим себе дерево рекурсии, то увидим, что через вызов (т.е. каждый второй вызов) величина len уменьшается в два раза. Суммарное количество действий на одном уровне дерева рекурсии равно O(NK), где k — общее количество событий. Поскольку уровней в дереве O(logN), то общая асимптотика O(NKlogN).

Приветствую сообщество Codeforces!

В воскресенье, 19 октября, в 13:00 MSK состоится очередной раунд для участников обоих дивизионов.

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

В подготовке задач принимали участие HolkinPV, gridnevvvit, danilka.pro, Avalanche, IlyaLos, Fefer_Ivan и я.

Разбалловка стандартная: 500-1000-1500-2000-2500 (в обоих дивизионах).

UPD: Опубликован разбор задач.

Доброго времени суток, сообщество Codeforces!

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

Раунд начнется 8 декабря в 13:00 MSK

Задачи были подготовлены сотрудниками и студентами Саратовского государственного университета, включая MikeMirzayanov, Fefer_Ivan, NALP, HolkinPV и меня.

Разбалловка стандартная: 500-1000-1500-2000-2500.

UPD: Поздравляем победителей:

1. asalwaysdontbeahero
2. VKRNVO5
3. chnluyi
4. pkwv
5. Xe4NIK

UPD: Разбор задач.

370A - Ладья, слон и король

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

• Ладья может достичь любого поля не более, чем за два хода. Если стартовое и конечное поле находятся в одной строке или в одном столбце, то достаточно одного хода.
• Слон может достичь только клетки, окрашенные в тот же цвет, что и стартовая, и тоже не более чем за два хода. Если стартовое и конечное поле находятся на одной диагонали, то достаточно одного хода. Чтобы это выяснить, нужно проверить, что r₁ - c₁ = r₂ - c₂ ИЛИ r₁ + c₁ = r₂ + c₂.
• Королю достаточно сделать max(|r₁ - r₂|, |c₁ - c₂|) ходов.

    int r1, c1, r2, c2;
    cin >> r1 >> c1 >> r2 >> c2;
    if (r1 == r2 || c1 == c2) cout << 1; else cout << 2;
    cout << " ";
    if ((r1 + c1) % 2 != (r2 + c2) % 2) cout << 0; else {
        if (r1 + c1 == r2 + c2 || r1 - c1 == r2 - c2) cout << 1; else cout << 2;
    }
    cout << " ";
    cout << max(abs(r1 - r2), abs(c1 - c2)) << endl;

370B - Берляндское лото

В этой задаче полезно рассматривать карточки игроков как множества чисел. В таком случае, карточка a не может быть закрыта строго раньше карточки b, если b является подмножеством a. Таким образом, критерием того, что карточка может быть закрыта первой является тот факт, что не существует другой карточки, которая является ее подмножеством.

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

bool contains(vector<int> a, vector<int> b) // b in a?
{
    forn(i, b.size())
    {
        bool in = false;
        forn(j, a.size())
            if (a[j] == b[i])
                in = true;
        if (!in)
            return false;
    }

    return true;
}

370C - Варежки

Если максимальный цвет встречается не более раз, то каждый ребенок может получить левую и правую варежки разного цвета. Для этого отсортируем все левые варежки в порядке убывания частоты их цвета: для входа 1 2 1 2 3 1 3 3 1 получилось бы 1 1 1 1 3 3 3 2 2. Чтобы получить последовательность цветов правых варежек, сдвинем последовательность цветов левых варежек влево на количество самого популярного цвета (в примере это 4, поэтому получим 3 3 3 2 2 1 1 1 1). И теперь объединим эти две последовательности в пары (1 — 3, 1 — 3, 1 — 3, 1 — 2, 3 — 2, 3 — 1, 3 — 1, 2 — 1, 2 — 1). Легко показать, что при этом все пары будут состоять из варежек различного цвета.

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

370D - Сломанный монитор

У этой задачи есть большое количество правильных решений, но еще больше у нее неправильных решений :)

Один из способов решить её такой. Легко видеть, что в правильном ответе найдется две противоположные стороны, на которых есть символ w. Если бы это было не так, то рамку можно было бы сжать до меньшего размена. Таким образом, размер рамки это dx или dy, где dx = maxx - minx + 1 and dy = maxy - miny + 1 (minx, maxx, miny, maxy — это соответствующие координаты левой/правой/верхней/нижней буквы w). Очевидно, размер искомой рамки равен максимуму из dx, dy.

Хорошо, размер рамки ясен, а как быть с её положением? Попробуем найти ее левый верхний угол.

Множество возможных координат x левого верхнего угла — это {minx, maxx - size + 1, 0}. В самом деле, давайте начнем двигать искомую рамку влево, пока это возможно. Либо она упрется в w левым или правым краем, либо в левую границу монитора.

Аналогично, множество возможных координат y левого верхнего угла — это {miny, maxy - size + 1, 0}.

Таким образом решение принимает вид:

find minx, maxx, miny, maxy
dx = maxx-minx+1, dy=maxy-miny+1
size = max(dx, dy)
foreach x in {minx, maxx-size+1, 0}
    foreach y in {miny, maxy-size+1, 0}
        if frame_correct(x, y, size)
            print answer
            exit algorithm

Всё что осталось сделать, это написать функцию frame_correct, которая проверяет, что рамка с левым верхним углом в (x, y) и размером size является ответом. Для этого достаточно пройти по ней и проверить, что все ее клетки находятся в границах монитора и количество w на рамке совпадает с их общим числом.

Описанное решение работает за O(nm).

370E - Летнее чтение

Для каждого номера книги, который присутствует в последовательности, найдем самое левое и самое правое вхождения: для каждого номера получился отрезок из позиций, на котором он точно должен быть записан. Понятно, что если два каких-то отрезка пересеклись, или же длина какого-то отрезка больше 5, то ответа не существует. Можно еще отдельно обработать случай, когда все числа — нули. Тогда дневник можно заполнить жадно, отдавая на все книги (кроме, возможно, одной), по два дня.

Итак, у нас есть несколько блоков из чисел и промежутки между ними. Будем решать задачу при помощи динамического программирования (ДП). Состояние будем описывать парой чисел (i, j): i означает номер блока из номеров книг (пронумеруем блоки слева направо), а j означает, до какой позиции числа из i-го блока будут идти в итоге (если после этого блока есть непустой промежуток свободных позиций, то сколько-то первый из них могут содержать такие же номера книг). Очевидно, что j - i не превосходит 5, поэтому количество состояний линейное. Пусть D(i, j) равно true, если можно корректно заполнить все пропуски до i-го блока при условии, что i-й блок распространится вправо вплоть до позиции j, и D(i, j) равно false в противном случае. Чтобы определить D(i, j), давайте переберем еще и то, насколько i-й блок распространится влево (очевидно, что таких способов всего несколько). Затем переберем позицию, до которой будет идти (i - 1)-й блок (т.е. зафиксируем состояние D(i - 1, k), где D(i - 1, k), конечно, равно true). Чтобы понять, возможен ли переход в ДП, нужно выяснить, можно ли корректно заполнить остаток промежутка между блоками. Пусть (i - 1)-й блок состоит из чисел x, i-й блок состоит из чисел y, а оставшаяся длина промежутка равна f. Тогда промежуток можно заполнить тогда и только тогда, когда 2·(y - x - 1) ≤ f ≤ 5·(y - x - 1).

Если вы осознали, как работает это ДП, то вам не составит труда понять, как получить ответ.

363A - Соробан

Not so much to say about this problem. You need to extract the digits of the given number (read it as string or repeteadly divide by 10 and take the remainders). Then carefully do the mapping of digits to its' representation.

363B - Забор

Another easy problem. We need to calculate the sum of every consequtive segment of k planks. One way to do this is to calculate partial prefix sums: . Then the sum of heights of the planks i, i + 1, ..., i + k - 1 is s_{i + k - 1} - s_i - 1. The other approach is to calculate the sum of the first k planks: h₁ + h₂ + ... + h_k. By subtracting h₁ and adding h_k + 1 we get sum of k planks starting from the second plank. Then, by subtracting h₂ and adding h_k + 2 we get sum of k planks starting from the third plank, and so on.

363C - Исправление опечаток

The general idea of the solution is the following: while there are three consequtive equal characters, remove any one of them. After that we can only have typos of the second type. So, if we have one couple of equal characters immediately after another couple of equal characters (xxyy), we need to decide which character to remove, x or y? Let's find the leftmost typo of the second type in the string. It is easy to see that we can always remove the character from the second couple.

All these can be done in a single pass. Go through the characters of the given string and build the resulting string ans. Let's denote the current character as ch. If ch is equal to the last two characters of ans, skip ch. If ch is equal to the last character of ans and ans[length(ans) - 2] = ans[length(ans) - 3] (assume that ans is 1-indexed), skip ch. Otherwise, append ch to ans.

363D - Прокат велосипедов

Let's do a binary search over the number of boys that can rent a bike. So let's say that we want to check whether it possible for k boys to rent bikes. If some k boys can rent a bike, then the k "richest" boys (with the most amount of personal money) also can do that. It is easy to see that if they can rent bikes, they can rent k cheapest bikes (if we first sort the bikes in increasing order of price, it will be just the first k bikes).

So, take k richest boys and try to match them with k cheapest bikes, spending as much common budget as possible. The following algorithm works (try to understand and prove it before asking questions): take the boy with least number of money (of course, among the considered k richest) and try to give him the cheapest bike. If the boy has ehough personal money to rent this bike, use his money to do this. Otherwise, use all his money and take some money from the common budget. Continue this process with the second cheapest bike and the second "poorest among the richest" boys. This process can end in two ways: we will either run out of budget and fail to rent k bikes, or we will successfully rent these bikes.

363E - Два круга

At first, for each valid center cell (i, j) calculate circleSum[i][j] — sum of values inside the circle with center at (i, j). This can be done with the code like that:

 for (int i0 = r; i0 + r < n; i0++) {
            for (int j0 = r; j0 + r < m; j0++) {
                int sum = 0;
                int lj = j0, rj = j0;
                for (int i = i0 - r; i <= i0 + r; i++) {
                    while (dist2(i0, j0, i, lj) > r * r) lj++;
                    while (dist2(i0, j0, i, lj - 1) <= r * r) lj--;
                    while (dist2(i0, j0, i, rj) > r * r) rj--;
                    while (dist2(i0, j0, i, rj + 1) <= r * r) rj++;
                    sum += rowSum[i][rj + 1] - rowSum[i][lj];
                }
                circleSum[i0][j0] = sum;
            }
        }

This code iterates over all rows from top to bottom and keeps lj and rj — the leftmost and the rightmost columns in current row i that are inside the circle with center at (i0, j0). The function dist2 returns squared distance between two cells, rowSum[i][j] is equal to sum of first j cells in row i. In total, values lj and rj will be changed O(n + m) times, so the complexity of this part is O(nm(n + m)).

In the second part of the solution, for each row i we calculate several values:

• leftMax[i][j] — maximum of circleSum[i][k] for k ≤ i
• cntLeftMax[i][j] — the number of corresponding maximum values
• rightMax[i][j] — maximum of circleSum[i][k] for k ≥ i
• cntRightMax[i][j] — the number of corresponding maximum values

All these values can be calculated in O(nm) time.

The third part of the solution is the most tricky one. Let's say that the cell (i, j) is boundary cell for the circle centered at (i₀, j₀) if it belongs to this circle and is the leftmost or the rightmost such point in row i. It is easy to see that two circles A and B intersect if and only if there exists a boundary cell of the circle A that belongs to the circle B. As long as we have O(n + m) boundary cells for each circle, checking whether two given circles intersect can be done in linear time. Now, for each pair (di, dj), which means the relative position of one center to the other, we can determine if such two circles intersect. There are O(nm) pairs (di, dj), so the total complexity of this part is O(nm(n + m)).

And, finally, in the fourth part we are going to calculate the answer. Let's iterate over all triples of values (i₀, j₀, i), where (i₀, j₀) is a valid center cell and i is a row number. Consider the set of cells (i, j) in the row i such that the circle centered at (i, j) intersects with the circle at (i₀, j₀). It is clear that this set is consists of some (possibly zero) consequtive cells in a row. Let's assume that these cells are (i, lj), (i, lj + 1), ..., (i, rj), values lj and rj can be found in the third part of the solution. We are interested in cell that are not in this set: (i, j) with j < lj or j > rj. To find the maximum sum in such circles in O(1), we use arrays computed in the second part. Overall complexity of the solution is O(nm(n + m)).

Доброго времени суток, сообщество Codeforces!

Рад Вам сообщить, что мы в очередной раз делаем раунд из задач одной из олимпиад для саратовских школьников. На этот раз — раунд для второго дивизиона. Раунд начнется в необычное для Codeforces время: 11 ноября в 12:00 MSK

Задачи были подготовлены MikeMirzayanov и мной, в написании альтернативных решений нам помогали Fefer_Ivan и Gerald.

Участники из первого дивизиона, как обычно, могут поучаствовать вне конкурса.

Разбалловка стандартная: 500-1000-1500-2000-2500.

UPD: Опубликован разбор на английском.

UPD 2: В задаче E изначальное авторское решение (оно, к сожалению, было одно) было неправильным. Однако, ответы ко всем претестам были корректные. После контеста авторское решение было исправлено, все решения по задаче E были перетестированы.

UPD 3: Появились окончательные результаты, рейтинг обновлен.

357A - Кружок школьников

В задаче нужно было перебрать все варианты проходного балла от 1 до 100 и для каждого варианта посчитать, какие получаются размеры групп. Если нашли подходящие разбиения, выводим соответствующий одном из них проходной балл, иначе выводим 0.

357B - День Флага

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

356A - Рыцарский турнир

Пусть в очередной битве (l, r, x) сражается K рыцарей. Тогда в этой задаче было достаточно научиться находить всех этих рыцарей за время O(K) или O(KlogN). Рассмотрим несколько способов сделать это.

Способ первый: хранить множество рыцарей в std::set (C++) или в TreeSet(Java). Тогда в C++ мы можем использовать метод lower_bound для нахождения самого первого живого рыцаря в отрезке, а потом итерироваться по множеству, переходя каждый раз к следующему по номеру живому рыцарю. В Java мы бы для этих целей использовали метод subSet.

    set<int> alive;
    for (int i = 0; i < n; i++)
        alive.insert(i);
        
    for (int i = 0; i < m; i++) {
        int l, r, x;
        scanf("%d%d%d", &l, &r, &x);
        l--, r--, x--;        
        set<int>::iterator it = alive.lower_bound(l);
        vector<int> toErase;        
        while(it != alive.end()){
            int cur = *it;            
            if(cur > r)
                break;                
            if(cur != x){    
                toErase.pb(cur); answer[cur] = x;
            }
            it++;
        }

        for (size_t j = 0; j < toErase.size(); j++)
            alive.erase(toErase[j]);
    }

Способ второй: определим массив next, значения в котором будут иметь следующий смысл:

• если рыцарь v живой, то next[v] = v;
• если рыцарь v выбыл, то next[v] указывает на некоторого рыцаря u > v (next[v] = u), такого, что между v и u нет живых рыцарей.

Тогда для того, чтобы для рыцаря v найти следующего по номеру живого рыцаря, нужно пройти по ссылкам next до первого живого рыцаря. Чтобы не ходить многократно по одним и тем же ссылкам, применяем эвристику сжатия путей из DSU. Надо учитывать случай, когда текущий рыцарь последний и уже выбыл из турнира.

    int getNext(int v){
        if(next[v] == v)
            return v;
        return next[v] = getNext(next[v]);
    }

    ...

     int cur = getNext(l);
     while(cur <= r){
        if(cur == x){
            cur = cur + 1;
        }else{
            answer[cur] = x;
            next[cur] = cur + 1;
        }

        cur = getNext(cur);
    }

356B - Ксюша и Хемминг

Обозначим первую строку за x, |x| = lenX, вторую строку за y, |y| = lenY. Пусть L=НОК(lenX, lenY). Очевидно, что для тех больших строк a и b, которые описаны в условии, L является периодом, поэтому достаточно решить задачу для длины L, а затем умножить ответ на . Зафиксируем позицию i в строке x и посмотрим, с символами в каких позициях в строке y будет сравниваться символ x_i. Из несложных соображений теории чисел это будут такие позиции 0 ≤ j < lenY, что i ≡ j (mod g), где g=НОД(lenX, lenY). Для каждого возможного остатка r от деления на g и каждого символа c можно посчитать count(r, c) — количество символов c, которые встречаются в y на позициях j таких, что j mod g = r. Тогда при вычислении расстояния Хэмминга напротив символа x_i будет ровно count(i mod g, x_i) таких же символов, а все остальные сравнения прибавят единицу к расстоянию Хэмминга.

private void solve() {
        Scanner in = new Scanner(System.in);
        long n = in.nextLong(), m = in.nextLong();
        String x = in.next(), y = in.next();
        int lenX = x.length(), lenY = y.length();
        int g = gcd(lenX, lenY);
        long L = lenX * (long)lenY / g;
        long answer = L;
        int[][] count = new int[g][26];
        for (int j = 0; j < lenY; j++) {
            count[j % g][y.charAt(j) - 'a']++;
        }
        for (int i = 0; i < lenX; i++) {
            answer -= count[i % g][x.charAt(i) - 'a'];
        }
        System.out.println(answer * (n * lenX / L));
    }

356C - Купе

В данной задаче требовалось придумать какой-нибудь правильный жадный алгоритм. Один из правильных подходов делает следующее:

1. Сначала соединяет все <<двойки>> с <<единичками>> (образуются <<тройки>>), путем пересаживания <<единичек>>.
2. Рассматривает два случая в зависимости от того, <<единичек>> больше изначально или <<двоек>>. Если больше единичек, то пробует соединять оставшиеся после первого пункта одинокие <<единички>> в тройки, если <<двоек>>, то пробует из каждых трех <<двоек>> образовать две <<тройки>>.
3. После применения пункта два, могут остаться еще какие-то <<единички>> или <<двойки>>. Нужно разобрать случаи того, что осталось, руками (случаев будет мало).

В задаче нужно руководствоваться скорее здравым смыслом, нежели какими-то известными жадными соображениями. Неплохо помогает написать стресс-тестирование с наивным решением (обходом в ширину), чтобы убедиться в корректности вашей жадности.

356D - Монеты и мешочки

Очевидно, что мешки и отношения "лежит непосредственно в" образуют лес. К каждой вершиной должно быть связано некоторое число c_i — количество монет в соответствующем мешке. Тогда, если мы для каждой вершины посчитаем величину f_i — сумма значений c_j в поддереве этой вершины, то должны выполняться следующие условия:

• f_i = a_i
• сумма f_i по вершинам, которые являются корнями деревьев, равна s.

Очевидно, что мешок с наибольшим a_i будет корнем какого-то из деревьев. Также достаточно легко понять, что решение задачи существует тогда и только тогда, когда можно выбрать такой набор a_i1, a_i2, ..., a_ik, что сумма a_i1 + a_i2 + ... + a_ik равна s, причем один из мешков с наибольшим a_i входит в такой набор. В одну сторону это очевидно, в другую покажем конструктивно: пусть у нас есть такой набор. Тогда все мешки, вошедшие в набор, кроме самого большого, будут "отдельными", то для них c_i = a_i, а все не вошедшие мешки мы последовательно положим друг в друга и в первый, получив матрешку (т.е. дерево с корнем в самом большом мешке будет ориентированной цепью).

Задача свелась к задаче о наборе суммы s из предметов a₁, ... a_n. Это задача является NP-полной, и обычно в подобных ограничениях решается так: пусть T(i, j) = 1, если можно набрать сумму j, используя какие-то из первых i предметов, и T(i, j) = 0 в противном случае. Тогда . Заметим, что i-ая строка этой таблицы зависит только от (i - 1)-ой, поэтому можно хранить в памяти не всю таблицу, а только две строки. Дальше мы будем использовать то, что значения в таблицы — это нули и единицы, поэтому мы можем хранить строчки таблицы побитово, в массиве из 4-битных целых чисел. Тогда, чтобы получить очередную строчку, мы должны сделать побитовое ИЛИ предыдущей строки и предыдущей строки, сдвинутой на a_i бит. Все это можно сделать за действий, поэтому выяснить, можно ли набрать сумму s, можно примерно за операций. Однако, тут нужно применить один трюк для того, чтобы восстановить, какие именно предметы нужно взять. Давайте для каждого значения суммы j будем запоминать величину first(j) — номер такого предмета, после рассмотрения которого стало возможно набрать сумму j. Это позволит нам восстановить ответ.

356E - Ксюша и строковая задача

Во время контеста большинство участников писали решение задачи очень похожее на авторское. Одно из авторских решений (более простое) использует полиномиальные хеши (хотя есть решения и без них). Кратко опишем решение.

1. Для каждой позиции i посчитаем с помощью хешей максимальное такое L_i, что подстрока s[(i - L_i + 1)..(i + L_i - 1)] является строкой Грея. Так же посчитаем максимальное такое P_i, что подстрока s[(i - P_i + 1)..(i + P_i - 1)] отличается от строки грея не более чем на один символ. Очевидно, что P_i ≥ L_i. Причем если P_i > L_i, то также сохраним позицию символа и символ, который различает подстроку и некоторую строку Грея.

2. Понятно, что если бы не нужно было менять символы, тогда ответ был бы равен , где f(L) = 1² + 3² + 7² + ... + L². Посчитаем ответ, без замены символов.

3. Теперь переберем позицию и новый символ, на который будем менять символ в данной позиции. Как понять, на сколько поменяется ответ на задачу? Посмотрим на все строки грея, вхождения которых перекрывают зафиксированную позицию. После изменения символа на другой, они все перестанут быть строками грея (вычтем их длину в квадрате из ответа). Посмотрим на все строки Грея, которые отличаются ровно в одной зафиксированном символе от некоторой подстроки строки. После изменения на этот символ они все добавятся в ответ (их длину в квадрате нужно добавить в ответ).

4. Суммируя вышесказанное, с помощью P_i L_i нужно, используя update на отрезке в offline, посчитать для каждой позиции и символа, на сколько поменяется ответ на задачу, если в данной позиции поставить этот символ. Далее нужно обновит ответ всеми возможными значениями.

Привет всем.

Сегодня в Саратове проходит региональная командная олимпиада школьников по программированию. Мы решили сделать раунд с использованием задач этого соревнования. Задачи к раунду готовили: Gerald (Геральд Агапов), Fefer_Ivan (Иван Фефер), HolkinPV (Павел Холкин), Igor_Kudryashov (Игорь Кудряшов), IlyaLos (Илья Лось) и Nerevar (Дмитрий Матов). Условия на английский переводила Мария Белова (Delinur).

Раунд начнется сегодня, 15 октября, в 16:00 MSK. К участию приглашаются участники обоих дивизионов.

Разбалловка стандартная: 500-1000-1500-2000-2500.

Поздравляем победителей!

Первый дивизион:

1. tourist
2. mmaxio
3. Dmitry_Egorov
4. iwiwi
5. bmerry

Второй дивизион:

1. Apsara
2. ZJUDBLab
3. noxe
4. intsashka
5. Kanari

UPD: Опубликован разбор задач.

254A - Карточки с числами

Для каждого x от 1 до 5000 заведем список таких индексов i что a_i = x. Проверим, что во всех списках четное количество элементов и выведем содержимое списков парами.

254B - Размер жюри

Для каждой олимпиады пробежим по всему периоду ее подготовки. Для этого нужно научиться по текущей дате получать предыдущую. Для каждого из дней подготовки увеличим на p_i количество различных членов жюри, которые должны работать в этот день. Тогда ответом на задачу будет максимальное из таких накопленных значений по всем дням. Не забудьте про 2012й год.

254C - Анаграмма

Обозначим количество символов x в строке s через C_s(x), а в строке t — через C_t(x). Тогда минимальное количество замен для получения анаграммы t из s есть . Теперь жадно построим лексикографически наименьшее решение. Будет идти в порядке возрастания позиции подбирать, какой символ будет в этой позиции в ответе. Найдем первый в порядке возрастания символ, которые может стоять на этом месте в оптимальном ответе. Для того, чтобы быстро проверять, может ли символ стоять или нет, мы будем все время пересчитывать величины C_s(x) и C_t(x) и вычислять, сколько необходимо замен по приведенной выше формуле.

254D - Крысы

Выберем произвольную клетку с крысой (например, верхнюю левую). Мы должны ее очистить. Сделаем из нее BFS, который не ходит на расстояние, большее d (назовем такой поиск в ширину d-BFS). Он посетит около 2d² в худшем случае. Мы должны взорвать первую гранату в одной из этих клеток. Переберем все варианты. Сделаем d-BFS из клетки-кандидата. Некоторые клетки с крысами не будут очищены взрывом и, соответственно, не будут посещены обходом. Значит, они должны быть очищены взрывом второй гранаты. Выберем произвольную клетку с крысой, которая не была очищена. Сделаем из нее d-BFS. Все посещенные клетки — это кандидаты на место подрыва второй гранаты. Проверим их все. Для проверки опять же запустим d-BFS. Если он посетил все клетки, не очищенные взрывом первой гранаты, то мы нашли решение.

Каждый d-BFS посещает не более 2d² клеток, поэтому общее число шагов будет около 8d⁶.

254E - Общежитие

Задача может быть решена динамическим программированием: пусть D(n, r) — максимальный рейтинг, которого Вася сможет достичь за первые n дней при условии, что со дня с номером n осталось ровно r килограмм еды. Подумаем теперь, кого Васе кормить в следующий день. Очевидно, что если он решит покормить k друзей, то ему выгодней покормить первый k друзей с наименьшей прожорливостью в этот день. Переберем все возможные k и сделаем соответствующие переходы. Всего получается 400² и 400³ переходов.

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

253A - Мальчики и девочки

Пусть мальчиков больше, чем девочек (противоположный случай решается аналогично). Тогда один из оптимальных ответов такой: мы будем добавлять детей парами мальчик-девочка (BG, в таком порядке) до тех пор, пока не кончатся девочки, за затем поставим в конец оставшихся мальчиков. К примеру, если имеется 7 мальчиков и 4 девочки, то мы построим ответ BGBGBGBGBBB.

253B - Физпрактикум

Для каждого x от 1 до 5000 посчитаем count(x) — количество результатов измерений, равных x. После этого переберем m — минимальный результат измерений от 1 до 5000. При фиксированном минимальном числе мы можем легко понять, какие числа следует удалить. А именно, нужно удалить все числа k такие, что k < m или k > 2·m. Чтобы посчитать количество таких чисел, мы используем суммируем count(k) по всем таким k.

253C - Текстовый редактор

Одно из возможных решений: поиск в ширину в графе, в котором вершинами являются пары (r, c), задающие номер строки и позицию в ней курсора. Из каждой вершины имеется не более четырех переходов, соответствующие нажатиям клавиш. Получается максимум около 10⁷ вершин и около 4·10⁷ переходов. Также задача может быть решена с использованием естественных жадных соображений.

253D - Таблица с буквами - 2

Переберем пару строк i, j (i < j), которые будут ограничивать нашу подтаблицу сверху и снизу. Для каждого символа ch от a до z выпишем в порядке возрастания номера таких столбцов k, для которых T[i, k] = T[j, k] = ch. Рассмотрим полученный список для какого-то символа ch. В этом списке мы должны посчитать количество пар столбцов l, r (l < r) таких, что в подтаблице с углами (i, l) и (j, r) содержится не более k символов «a». Это может быть сделано за линейное время с помощью метода двух указателей.

253E - Принтер

Сначала научимся моделировать процесс при полностью известных приоритетах. Будем хранить очередь заданий в принтере в виде очереди с приоритетами. Задание будет попадать в нее при поступлении и исчезать при завершении печати последней страницы из него. Тогда любое изменение в очереди происходит по наступлении одного из двух событий: какое-то задание поступило или какое-то задание закончило печататься. Между двумя последовательными такими событиями принтер просто печатает страницы из наиболее приоритетного задания. Поэтому, если мы будем поддерживать set событий, то весь процесс печати можно смоделировать за O(NlogN).

Теперь решим исходную задачу. Сделаем очевидное наблюдение: чем выше приоритет у задания, тем раньше закончится его печать. Тогда приоритет, который мы ищем, может быть найден бинарным поиском. Осталось лишь заметить, что существует всего O(N) значений приоритета, среди которых нужно искать. Итоговая сложность решения — O(Nlog²(N)).

Отмечу, что у этой задачи есть и решение за O(NlogN), которое я напишу позже.

Всем привет.

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

Первый из раундов — Codeforces Round #154 (Div. 2) — состоится 8 декабря в 14:00 MSK.

Второй — Codeforces Round #155 (Div. 2) — пройдет 9 декабря в 14:00 MSK.

Это будут обычные раунды по правилам Codeforces, но с одной особенностью:

Ввод-вывод во всех задачах будет файловый: чтение нужно осуществлять из файла input.txt, а выводить в файл output.txt.

Разбалловка будет объявлена незадолго до начала каждого из раундов.

Участники из первого дивизиона, как обычно, могут поучаствовать вне конкурса.

UPD По ссылкам содержатся примеры решений с файловым вводом-выводом для некоторых языков:

• C++: 2366378
• Pascal: 2454867
• Java: 2366738
• Python: 2387503
• D: 2436251
• Scala: 2385341
• Haskell: 2378010
• C: 2519130
• Ruby: 2375494
• PHP: 2381582
• C# 2716641

UPD2 Разбалловка в 155-м раунде будет стандартной: 500-1000-1500-2000-2500.

UPD3 Появился разбор задач раунда 154.

UPD4 К сожалению, в первой половине контеста было обнаружено, что чекер по задаче C не проверяет лексикографическую минимальность выведенного участником ответа. Мы приносим свои извинения за эту ошибку. Поправив чекер, мы провели расследование и обнаружили, что изменение чекера повлияло на 53 участников из второго дивизиона. Мы считаем, что справедливо будет сделать данное соревнование для таких участников нерейтинговым. На всех остальных участников эта неточность никак не повлияла.

UPD5 Появился разбор задач раунда 155, уже на русском:)).

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

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

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

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

UPD:

Чувствую, что пост над закончить, как бы мне ни хотелось этого не делать. Да, в этот раз мы остались без медалей. Как не было ни разу у команд СГУ бронзовых медалей, так и не стало:) Закономерность насчет неудачных для нас високосных годов подтвердилась (в 2004-м и в 2008-м команды вообще не выходили в финал).

Путь этой команды в ACM ICPC закончен, так же как и цикл напряженной работы и подготовки. Теперь начинается новый цикл. С другими командами, которые должны подтянуться до топового уровня, с новыми надеждами. Это бы не наш год и не наш финал, но мы с оптимизмом смотрим в будущее, потому что знаем, как добиваться успеха.

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

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

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

• Максим Иванов (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.