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

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), которое я напишу позже.