160A - Twins

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

160B - Unlucky Ticket

Запишем в массив a первые n цифр, а в массив b — последние n цифр, и отсортируем эти массивы. Нетрудно понять, что если для всех i выполняется a[i] < b[i], или для всех i выполняется a[i] > b[i], то билет точно является несчастливым. Но также нетрудно понять, что для любого несчастливого билета выполняется или первое условие, или второе. Таким образом, мы придумали критерий несчастливости, можно реализовать за время O(n·log(n)).

160C - Find Pair

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

Пусть число k и массив a заданы в 0-нумерации, а сам массив отсортируем. Тогда если все числа различны, то очевидный ответ – это пара (a[k / n], a[k % n]), где операция % означает остаток по модулю. Однако, если в массиве есть повторяющиеся числа, то ситуация становится немного хитрее, рассмотрим пример: пусть дан массив (1, 1, 2, 2), тогда пары записаны следующим образом: (1, 1), (1, 1), (1, 1), (1, 1), (1, 2), (1, 2), (1, 2), (1, 2), (2, 1), (2, 1), (2, 1), (2, 1), (2, 2), (2, 2), (2, 2), (2, 2), каждая пара учитывается и никуда не девается, всегда рассматриваются ровно n² пар чисел.

По-прежнему верно, что первое число – это a[k / n]. А второе число – это a[(k–n·cnt) / num], где cnt – количество чисел в массиве строго меньших, чем a[k / n], а num – количество чисел в массиве, которые равны a[k / n].

В этой формуле несложно убедиться, рассмотрев пару примеров с повторяющимися элементами. В крайнем случае, можно написать тривиальное решение за O(n²·log(n)) и убедиться, что вы правильно придумали формулу.

P. S. Претест 3 имеет вид: в массиве (1, 1, 2) нужно найти 3-ю по лексикографичности пару. Она равна (1, 1).

160D - Edges in MST

Во-первых, разберем случай, когда все веса одинаковы. Тогда очевидно, что любое ребро может быть в дереве, но в случае, если ребро – мост, то оно является единственным способом соединить две компоненты, а значит, оно принадлежит любому MST. Итак, для мостов ответ равен «any», а для всех остальных – «at least one».

Рассмотрим алгоритм Краскала (или Крускала – кто как привык). В нем в MST пытаются добавляться ребра в порядке возрастания их весов. Но если у двух ребер вес одинаковый, то их порядок добавления может быть любым, а значит, одно ребро может зависить от того, добавилось раньше другое ребро того же веса, или оно добавится позже.

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

Построим на каждом слое отдельный граф, причем вершинами будут являться уже сформированные на данный момент компоненты связности, а ребра добавляются между соответствующими компонентами. Если ребро – петля, то значит, что существует способ связать два конца этого ребра за меньшую стоимость, и это ребро никогда нам не нужно, ответ для него – «none».

Если ребро в построенном графе – мост, то по ранее разобранному случаю, ответ для него «any», а для всех остальных – ответ «at least one». При разборе этих случаев нужно быть аккуратным, потому что при сжатии графа появляются мультиребра, ответ для них всегда «at least one», потому что ни одно из повторяющихся ребер не является мостом.

Решение это задачи можно реализовать за время O(n·log(n)).

160E - Buses and People

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

Для каждого автобуса создадим событие вида «при координате s_i появляется автобус, который поедет в момент времени t_i и уедет до точки f_i». Для каждого человека создадим событие вида «при координате l_i появляется человек, который поедет в момент времени b_i и уедет до точки $r_i$».

Эти события отсортируем в порядке возрастания координаты (s_i, если это автобус, и l_i, если это человек) и будем выполнять в этом порядке.

Будем поддерживать структуру данных, в которой для каждого времени t_i будем хранить максимальное f_i автобуса, который едет в этот момент. Тогда если текущее событие означает автобус, то нужно просто обновить соответствующее значение в структуре данных. А если текущее событие означает человека, который в момент времени b_i поедет до остановки r_i, то нужно с помощью структуры данных отвечать на запрос «найти в структуре минимальную позицию t, которая не менее b_i, а соответствующее ему значение не менее r_i», тогда соответствующий этому t номер автобуса и есть ответ.

Вопрос в том, какую структуру данных использовать. Проще всего это делать с помощью дерева отрезков по максимуму, тогда на этот запрос можно отвечать за время O(log(n)), но также можно было использовать и другие структуры данных, например декартово дерево с неявным ключом и др.

Таким образом авторское решение работает за время O((n + m)·log(n + m)).

Существует достаточно простое решение с двумерным деревом отрезков, работающее за O((n + m)·log²(n + m)), но не гарантировалось, что оно уложится в Time Limit.