Задача А.

В этой задаче нужно было лишь удостовериться, что ∑x_i  = 0, ∑y_i  = 0 и ∑z_i  = 0.

Явно это условие не писали, чтобы у участников была возможность для взломов.

Задача B.

В этой задаче, фактически, требовалось найти победителя на каждом этапе. Для каждого участка это делается полным перебором всех участников для нахождения участника с минимальным временем прохождения участка, который бежал этот участок. Асимптотика решения O(nm).

Задача C.

В этой задаче требовалось после каждой покупки обновлять набор артефактов у всех друзей Кости. Нужно завести матрицу c[i][j] – количество j-ого базового артефакта, требуемого для того, чтобы собрать i-ый составной артефакт. Далее можно было завести матрицу составных артефактов, где a[i][j] – количество j-ого базового артефакта у i-ого друга и аналогичную матрицу b составных артефактов, и после каждой покупки  i-ого друга проверять собрался ли у него какой-нибудь составной артефакт за O(MN). Для этого нужно проверять собрался ли один составной артефакт за O(N). Это делается следующим образом: для i-ого друга нужно проверить, существует ли u, что c[j][u] > a[i][u]: если да, то j-й артефакт не будет собран, если нет, то нужно увеличить b[i][j] и обновить значения в a[i]). То есть асимптотика обработки всех покупок O(NQM). Далее требуется для каждого человека составить список артефактов, храня при этом их количество(суммарно O(KN + KM), которые у него есть, и отсортировать его (суммарно O(QlogQ)).

Задача D.

Данная игра конечна, так как за исключением конечного количества(2) отражений относительно прямой y=x, координаты изменяются на неотрицательное целое число (причем минимум 1 координата изменяется на положительное число).

Алгоритм решения этой задачи – DFS/BFS по состояниям, где состоянием является пара координат и две логических переменных, обозначающих то, отражал ли уже 1 (2) игрок точку относительно прямой y=x.

Всего состояний получается S <= 4D² (пар координат) * 4(значений булевых переменных).

Обработка одного состояния занимает O(N) действий (только не нужно забывать пробовать отразить точку относительно прямой y=x, если данный игрок это ещё не сделал ранее в ходе игры). Таким образом, общая асимптотика O(ND²), что работает на С++ менее 200мс.

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

Задача Е.

Для решения этой задачи требуется постепенно «передвигать» подотрезок и поддерживать:

1)множество В чисел, встречающихся один раз с функцией извлечения максимума за O(logN),

2)множество А чисел, встречающихся на данном подотрезке с хранением количества раз, которое данное число встречается на данном подотрезке с функцией проверки того, сколько раз встречается число на данном подотрезке за O(logN).

При движении отрезка с (a[i] .. a[i + k – 1]) на 1 элемент влево(a[I + 1]..a[I + k]) требуется:

1) Проверить, совпадает ли a[i]  с a[I + k]. Если да, то не требуется изменять множества,  иначе переходим к п.2 и 3.

2) Проверяем в множестве А, сколько раз встречается a[i]: если 2, то добавляем a[i] в В, если 1, то удаляем из A и В. Не забываем уменьшить соответствующее количество вхождений a[i] в текущий отрезок на 1.

3)Проверяем в множестве А, сколько раз встречается a[I + k]: если 0, то добавляем a[i] в В и в А, если 1, то удаляем из В. Не забываем увеличить соответствующее количество вхождений a[i] в текущий отрезок на 1.

 После этого, если множество В не пусто, извлекаем из него максимум.

Таким образом, асимптотика алгоритма O(NlogN). В качестве таких структур данных подходит set/map для тех, кто пишет на С++, и декартово дерево.