362A - Встреча полуконей

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

362B - Петя и лестницы

Обратим внимание на то, что число грязных ступенек  ≤ 3000. Для того, чтобы решение существовало, необходимо проверить, что ступенька с номером 1 и ступенька с номером n чистые, а также что в отсортированном массиве не встречается больше двух подряд идущих ступенек. Отсортируем массив, и проходом по нему узнаем нет ли трех подряд идущих номеров грязных ступенек, а также проверим, не являются ли ступеньки 1 и n грязными.

362C - Сортировка вставками

Количество выполнений функции swap — это количество инверсий во входной перестановке. Несложно заметить, что менять местами имеет смысл только такие элементы a_i, a_j, что i < j и a_i > a_j (иначе количество инверсий только увеличится). Пусть d_i, j — количество таких элементов перестановки с индексами от 0 до i включительно, которые строго меньше j. Тогда при обмене элементов c индексами i и j количество инверсий станет равным old - 2 * (d_i, ai + d_j, aj - d_i, aj - d_j, ai) - 1, где old — количество инверсий в исходной перестановке. Достаточно перебрать все пары элементов и выбрать из них те, которые позволяют минимизировать количество инверсий. Доказательство этой формулы оставим читателю в качеству упражнения.

362D - Дураки и дороги

Если исходный граф состоит менее чем из q компонент связности, то решения не существует. В противном случае, очевидно, выгодно сначала добавлять ребра, которые будут соединять разные компоненты, а затем ребра в пределах одной компоненты. Первый этап можно выполнять жадно: каждый раз брать две компоненты, текущий вес которых минимален, и соединять их ребром, объединяя в одну компоненту. Для этого, например, все компоненты связности текущего графа можно хранить в структуре set. Для выполнения второго этапа достаточно найти любую компоненту, состоящую более чем из одной вершины (т.к. петли запрещены), и добавить все оставшиеся ребра между любыми двумя её вершинами. Если какое-то действие выполнить невозможно (например, были добавлены все ребра, а количество компонент связности все равно больше требуемого), то решения также не существует.

Асимптотика — O(n + m + plogn).

362E - Петя и трубопровод

Представим данную задачу как задачу нахождения максимального потока минимальной стоимости. Построим следующую сеть. Истоком будет 1-ый резервуар, стоком — n-ый резервуар. Каждая труба из резервуара u в резервуар v в сети будет представлена двумя дугами из вершины u в вершину v — первое ребро будет иметь пропускную способность c_uv и стоимость 0, второе — бесконечную пропускную способность и стоимость 1. Таким образом, ответом на задачу будет величина максимального потока в этой сети стоимости не более чем k. Ее можно найти стандартным алгоритмом увеличивающих путей.

UPD1. Добавлен разбор задач A и B. UPD2. Добавлен разбор задачи C.