Белорусская областная олимпиада 2018

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Привет всем. На этой неделе (8-12 января 2018 года) проходит областная олимпиада по информатике в Беларуси. Олимпиада проходит во всех областях (а их у нас всего шесть) в одно и то же время с одним и тем же набором задач. Здесь можно обсудить олимпиаду, ознакомиться с уловиями задач (надеюсь, что все участники олимпиады ознакомятся с условиями на самой олимпиаде) и, может быть, если я смогу решить, с решениями.

Всем участникам желаю удачи!

Условия и решения задач для каждого из туров появятся не раньше их завершения.

Первый тур

Задача 1. Два квадрата

Решение

Задачу можно решать разными способами, но я попоробую рассказать самое короткое решение, которое только смог придумать.

Найдем bounding box закрашенных клеточек. Пускай мы будем знать его левую границу l, правую границу r, верхнюю границу u и нижнюю границу d. Теперь заметим, что у нас может быть только два случая:

Левая верхняя клетка одного квадрата находится в (u, l), правая нижняя клетка другого квадрата находится в (d, r).
Левая нижняя клетка одного квадрата находится в (d, l), правая верхняя клетка другого квадрата находится в (u, r).

Рассмотрим первый случай. Мы уже знаем, что первый квадрат находится в (u, l). Осталось найти, где находится второй квадрат. Для этого переберем размер k квадратов. Теперь осталось заметить, что нам достаточно проверять, закрашены ли клетки на границах bounding box'a (не все, а лишь те, что находятся на расстоянии k от уголков), чтобы определить, не взяли ли мы слишком большое k. Теперь мы с легкостью можем восстановить позицию второго квадрата: (d - k + 1, r - k + 1).

Второй случай аналогичен первому.

Сложность решения: O(n²).

Решение на C++.

Задача 2. Творческие выходные

Подсказка 1

Какие планки нам выгодно красить в первую очередь? А какие в последнюю?

Решение

Подсчитаем, какое количество планок нам нужно для i-го цвета. Теперь заметим, что закрашенные в нужный цвет планки мы уже никогда не сможем перекрасить. Поэтому будем красить жадно, стараясь «правильно» закрашивать как можно меньшее количество планок. Для этого отсортируем цвета по частоте во входных данных. Ну а дальше проходим и за линейное время считаем ответ.

Сложность решения: $\text{[math]}$ .

Решение на C++.

Задача 3. Непростая сумма

Подсказка 1

Возможно, с упорядоченными данными проще работать...

Подсказка 2

Попробуем зафиксировать какое-то число. Пусть это будет i. Есть числа меньшие, чем i, а есть...

Подсказка 3

Попробуем разбить все числа на группы размера i. Возможно, в таких группах будет проще подсчитывать сумму остатков.

Решение

Моя любимая задача на этом туре. Реализация — короткая, а идея — суперская.

Воспользуемся сортировкой подсчетом. Ответ будем считать как $\text{[math]}$ , где $\text{[math]}$ , a cnt_i — количество чисел равных i. Осталось эффективно подсчитывать sum_i.

Заметим, что все числа меньшие i дают в качестве остатка свое собственное значение, поэтому нам достаточно подсчитать сумму всех чисел, меньших i. С большими числами поступим похитрее. Разобьем их на такие отрезки: [i, 2·i), [2·i, 3·i), [3·i, 4·i), ... Научимся быстро находить ответ для таких отрезков.

Раcсмотрим отрезок [k·i, (k + 1)·i). Заметим, что число k·i + j при делении на i дает остаток j. Поэтому, если мы просто прибавим к ответу число k·i + j, то ответ будет увеличен на k·i больше, чем нужно. Поэтому, если мы сложим все числа из отрезка [k·i, (k + 1)·i), то нам нужно будет убрать (k·i)·cnt_{k·i..(k + 1)·i}. Поэтому сумму остатков на таком промежутке можно вычислить как sum_{k·i..(k + 1)·i} - (k·i)·cnt_{k·i..(k + 1)·i}.

Такое решение требует O(n) времени на сортировку и $\text{[math]}$ на вычисление ответа.

Решение на C++.

Задача 4. Роборалли

Подсказка 1

Количество начальных вершин совпадает с количеством путей, да? Вместо того, чтобы сортировать строки, попробуйте отсортировать вершины. А зная k-ю начальную вершину можно и сам путь найти.

Подсказка 2

Если склеить два ребра длинны 1, то получится одно ребро длины 2. А если два длинны 2, то получится одно длины 4...

Подсказка 3

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

Решение

Что-то я разленился. Если в кратце, то задача аналогична построению суффиксного массива. Что забавно, но можно написать решение, которое практически не зависит от m. Давайте будем считать m = 2²⁰, что даже больше, чем может быть во входных данных. Удлинять ребра в два раза будем точно так же как и в методе двоичного подъема.

Сложность по времени: $\text{[math]}$ .

Решение на C++.

Второй тур

Задача 1.

Решение

Нужно заметить, что для того, чтобы решить задачу, нам достаточно взять какой-то один столбец и какую-то одну строку. Затем за O(n²) можно перебрать пару элементов, которые нужно переставить в этой строке и в этом столбце.

Сложность по времени: O(n²).

Задача 2.

Решение

Будем хранить счетчик вложенности. А можно еще хитрее. Если встретили открывающую скобку, то уменьшаем k, если закрывающую — увеличиваем. В таком случае, если мы встретили единичку, то к ответу прибавляем 4^k = 2^2·k. Таким образом, задачу можно решить в один проход.

Сложность по времени: O(n).

Задача 3.

Подсказка 1

Обратите внимание на то, что числа отличаются не больше, чем на 1.

Подсказка 2

Если для i j таких, что i ≤ j, выполняется условие a_i ≤ a_j, то можно утверждать, что ответ не менее a_j - a_i + 1

Подсказка 3

Предположим, что мы посчитали ответ для двух соседних отрезков. Что нам нужно знать, чтобы быстро посчитать ответ для объединенного отрезка?

Решение

Научимся объединять соседние отрезки. Пусть мы знаем ответ для отрезка [l, m) и отрезка [m, r). Попробуем получить ответ для отрезка [l, r). Тут всего три простых случая:

Максимальный ответ находится в левом отрезке;
Максимальный ответ находится в правом отрезке;
Максимальный ответ пересекает границу m.

Для первых двух случаев ответ очевиден, а для третьего ответ находится так:

max{a_m, a_m + 1, ..., a_r - 1} - min{a_l, a_l + 1, ..., a_m - 1} + 1

Чтобы быстро отвечать на запросы построим дерево отрезков, которое будет хранить минимум, максимум и ответ на отрезке. Таким образом, мы сможет отвечать на каждый запрос за время $\text{[math]}$ .