435A - Очередь на остановке

Эта задача решается за один проход по всем группам. Решение можно представить следующим кодом:

int result = 1;
int people = 0;

for(int i = 0; i < n; i++)
{
    if (people + a[i] <= m)
        people += a[i];
    else
    {
        result++;
        people = a[i];
    }
}

cout << result << endl;

435B - Паша максимизирует

Эта задача решается жадно. Будем стараться максимальные цифры ставить как можно раньше. Алгоритм можно описать так:

1) Рассмотрим каждую позицию по очереди, начиная с 1, пусть текущая позиция i
2) Среди следующих k цифр числа найдем ближайшую максимальную, пусть она находится на позиции j
3) Если эта цифра больше текущей цифры на позиции i, то сделаем серию обменов, поставим ее на позицию i, одновременно умешьшим величину k, то есть выполним k = k - (j - i)

435C - Кардиограмма

Эта задача носила технический характер, нужно было реализовать описанное в условии. Для начала нужно было посчитать координаты всех точек ломанной. Также заведем матрицу для хранения ответа. Поскольку координата y могла становиться отрицательной, удобно было удвоить размеры матрицы и изначально сдвинуть картинку вверх на 1000. В конце нужно будет вывести ее без лишних пустых строк.

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

435D - Специальная сетка

Так как ограничения на n и m были не очень большие, должно было проходить решение за O(max(n, m)³), то есть перебор всех треугольников. А именно, нужно было перебрать все треугольники и проверить для каждого треугольника за O(1), что он удовлетворяет всем описанным условиям.

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

Полезные соображения, помогающие значительно сократить реализацию описанного выше:

• все треугольники, которые нужно посчитать — равнобедренные прямоугольные треугольники;
• либо катеты треугольника параллельны сторонам сетки, либо гипотенуза параллельна одной из сторон сетки;
• если научиться решать задачу, считая, что нужно посчитать количество треугольников только двух видов, то решение для всех треугольников можно получить, посчитав ответы для 4-х поворотов матрицы.

435E - Специальный граф

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

Вертикальные раскраски выглядят следующим образом:

acbcbd...
bdadac...
acbcbd...
bdadac...
acbcbd...
bdadac...
......

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

Горизонтальные раскраски выглядят аналогично, только повернуты на 90 градусов. Конечно, бывают раскраски, которые одновременно и горизонтальные и вертикальные, но для решения задачи, это не имеет никакого значения.

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

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

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