Автор: BekzhanKassenov
В этой задаче необходимо было найти чья шахматная позиция сильнее.
Решение: Пробегаемся по всей доске, складывая веса фигур игроков, и в конце выводим ответ.
Асимптотика: O(n2), где n — длина стороны доски (в этой задаче — 8)
Код: 10083191
Автор: ADJA
В этой задаче вам было дано 3 массива. Второй содержал все элементы первого, за исключением одного, третий массив содержал все элементы второго, за исключением одного. Необходимо было вывести удаленные элементы.
Решение: Я опишу простейшее решение этой задачи: Обозначим сумму элементов в первом, втором и третьем массиве как a, b и c соответственно. Ответом будут числа a - b и b - c
Также существуют множество других решений, использующих map, xor и прочее.
Асимптотика: O(N)
Код: 10083248
Автор: ADJA
В этой задаче вам необходимо было поделить n опытных участников и m новичков на команды.
Решение: Обозначим команды с 2 опытными участниками и 1 новичком как type1 и команды с 1 опытным участником и 2 новичками как type2. Зафиксируем количество команд type1 как i. Их количество не превышает m. Тогда количество команд type2 равно min(m - 2 * i, n - i). Осталось проверить все возможные варианты i и выбрать оптимальный.
Асимптотика: O(N)
Код: 10083265.
Автор: ADJA
В этой задаче необходимо было найти количество подстрок данной строки таких, что каждая подстрока начинается и заканчивается на одну и ту же букву и сумма весов букв в этой подстроке (кроме начала и конца) равно нулю.
Решение: Обозначим sum[i] как сумму весов первых i букв. Создадим 26 map < longlong, int > -ов, 1 на каждую букву. Пусть в данный момент мы находимся на позиции i и map текущего символа m. Тогда необходимо добавить к ответу m[sum[i — 1]], и sum[i] в m.
Асимптотика: O(Nlog(N)), где N — длина исходной строки.
Код: 10083293.
Автор: BekzhanKassenov
В задаче необходимо было отвечать на следующие запросы на дереве: для заданных пар вершин найти количество вершин, равноудаленных от них.
Принятые обозначения:
dist(a, b) — расстояние между вершинами a и b.
LCA(a, b) — наименьший общий предок вершин a и b.
depth[a] — расстояние от корня дерева до вершины a.
size[a] — размер поддерева, корнем которой является вершина a.
На каждой картинке вершины, покрашенные в зеленый цвет — вершины из ответа, вершины, покрашенные в синий цвет — вершины из запросов.
Препроцессинг: Для начала необходимо считать ребра дерева и построить по ним структуру данных для нахождения LCA (удобнее всего использовать двоичный подъем, так как в будущем он понадобится для других целей). Асимптотика: O(NlogN)
Ответы на запросы:
Для каждого запроса необходимо рассмотреть несколько случаев:
1) a = b. В этом случае ответ равен n.
2) dist(a, b) нечетно. Тогда ответом будет 0.
3) dist(a, l) = dist(b, l), где l = LCA(a, b).
Двоичным подъемом найдем сыновей вершины l, которые являются предками вершин a и b (обозначим их как aa и bb соответственно). Ответом будет n - size[aa] - size[bb].
4) Все остальные случаи.
Предположим, что depth[a] > depth[b]. Тогда найдем с помощью двоичного подъема dist(a, b) / 2-ого предка вершины a (обозначим его как p1), dist(a, b) / 2 - 1-ого предка вершины a (обозначим его как p2). Ответом будет size[p1] - size[p2].
Асимптотика: O(logN) на запрос, O(MlogN) на все запросы.
Итоговая асимптотика: O(MlogN + NlogN)
Код: 10083310.