Обсуждение контеста

Задача А. Вторая порядковая статистика

Тематика: Сортировка

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

Задача B. Стол для переговоров

Тематика: Симуляция, динамическое программирование

В этой задаче требовалось определить максимальный периметр прямогульника, который не содержит внутри себя единиц. Назовем прямоугольники, не содержащие единиц, допустимыми. Для решения надо было просмотреть все допустимые прямоугольники и выбрать максимальный периметр. Вопрос в том, как перебирать все допустимые прямоугольники. Говорят, что решение "в лоб" с помощью 6 вложенных циклов за 25⁶ проходит по времени. Очевидно, четыремя циклами мы фиксируем углы прямоугольника, а еще двумя проверяем его допустимость. Не совсем очевидно, что такое решение уложится по времени.

Можно было написать более аккуратное решение с помощью динамического программирования за O((n*m)²). Заметим, что прямоугольник с координатами (x1, y1, x2, y2) является допустимым тогда и только тогда, когда допустимыми явлюятся прямоугольники (x1, y1, x2-1, y2), (x1, y1, x2, y2-1) и в клетке (x2, y2) стоит '0'. Таким образом, пересчет допустимости производится за O(1), что суммарно будет происходить за время O((n*m)²), т.е. линейное от количества прямоугольников. 

Задача C. Системный администратор

Тематика: Симуляция

В этой задаче требовалось составить связный граф из n вершин, содержащего m ребер, такой, что при удалении вершины v граф перестанет быть связным или сообщить, что такой граф не существует. При этом не должно быть кратных ребер. Очевидно, что связный граф не может существовать, если число ребер меньше, чем n-1. Кроме того, нетрудно видеть, что максимальное число ребер достигается, когда по одну стороны от v находится одна вершина, а по другую - полный граф из оставшихся вершин. Это число равно (n-1)*(n-2)/2+1. Если число ребер лежит в допустимом диапазоне - граф всегда существует. Дальше нужно было аккуратно разместить одну вершину по одну сторону от v (пусть это вершина 1), а с другой стороны построить связный граф с m-1 ребром. Лучше всего это было сделать проведя сначала ребра из v во все остальные, кроме 1, а затем между всеми остальными (кроме 1).

Задача D. Отрезки

Тематика: Метод сканирующей прямой

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

Задача E. Схема

Тематика: Теория графов

В задаче E дан ориентированный граф, требовалось сделать его сильно связным, т.е. чтобы каждая вершина была достижима из любой другой, добавив минимальное число ребер. Из формата входных данных неявно следует очень важное условие: у любой вершины есть не более одного исходящего ребра. Значит, начав путь из некоторой вершины мы либо зациклимся, либо нам некуда будет идти. Отсюда следует, что любая компонента связности (обычной) имеет вид либо замкнутого цикла, либо несколько простых путей, входящих в вершину или цикл. Сначала рассмотрим все пути, выходящие из вершин, у которых нет входящих ребер. Проходя, будем красить вершины, пока либо нам некуда будет идти, либо придем в покрашенную вершину. Тогда вершина, из которой мы пошли, будет называться началом, а в которую пришли - концом компоненты.

После этого рассмотрим еще непокрашенные вершины - они точно принадлежат циклам. Началом и концом цикла назовем некоторую вершину, ему принадлежащую. Получили набор компонент, которые надо соединить. Будем соединять циклически: из конца i-й компоненты пустим ребро в начало ((i+1)%k)-й, где k - число компонент. Ответом будет k. Здесь есть исключение: если у нас только одна компонента, формирующая цикл, то ответ 0.

Таким образом каждое ребро мы просмотрим один раз и время работы составит O(n).

Upd: 

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

Говорят, что в задаче B решение с шестью вложенными циклами работает за 30 мс, т.е. с ним нет никаких проблем.