Прямой перебор

Заведём массив u размера N, где u_i = false, если i-й персонаж ещё стоит в кругу и u_i = true если выбыл. Для того, чтобы найти очередного выбывающего персонажа сделаем следующее: на каждой из M итераций мы ищем следующий элемент, равный false и помечаем его как true. Номер (ans) помеченного в N-й раз элемента (u_ans) и будет ответом.

Асимптотика: O(N ⋅ M) на поиск персонажа; O(1) на удаление персонажа.

Итоговая асимптотика на запрос: O(N ⋅ M), проходит только подзадачу 1.

Прямой перебор (M по остатку)

Если мы пройдём весь круг, то количество посчитанных персонажей уменьшится на кол-во оставшихся (т.е на N − i + 1 в i-й раз). Это значит, что можно не совершать лишние круги, а сразу обрезать их: M = M mod (N − i + 1). Стоит учесть, что если M кратно (N − i + 1), то остаток от деления будет равен 0, нужно сделать либо M = (N − i + 1), либо найти первого непомеченного персонажа в обратную сторону.

Асимптотика: O(N) с большой константой на поиск персонажа; O(1) на удаление персонажа.

Итоговая асимптотика на запрос: O(N) с большой константой. Проходит подзадачи 1-3.

Перебор с DSU

DSU (disjoint-set-union) — "система непересекающихся множеств". В данном случае мы создадим N изначальных множеств, в i-ом из которых будет находится лишь i-й персонаж. При удалении персонажа будем помещать его множество в множество последующего персонажа, который становится "родителем". Таким образом, для поиска очередного непомеченного персонажа достаточно лишь найти "родителя" текущего персонажа. На N-ой итерации останется лишь 1 большое множество со всеми персонажами, индекс "родителя" этого множества и будет ответом.

Асимптотика: O(M ⋅ log(N)) на поиск персонажа; O(log(N)) на удаление персонажа.

Итоговая асимптотика на запрос: O(M ⋅ log(N)). Проходит подзадачи 1-2.

Перебор с DSU (M по остатку)

Аналогично, обрежем от M лишние круги: M = M mod(N − i + 1).

Асимптотика: O(N ⋅ log(N)) на поиск персонажа; O(log(N)) на удаление персонажа.

Итоговая асимптотика на запрос: O(N ⋅ log(N)). Проходит подзадачи 1-4.

Перебор с вектором

Создадим вектор целых чисел, поместим в него N чисел от 1 до N. Перебираем M элементов и удаляем M-й по счёту. После N − 1-го удаления выведем оставшееся в векторе число — это и будет индекс оставшегося персонажа.

Асимптотика: O(M) на поиск персонажа; O(N) на удаление персонажа.

Итоговая асимптотика на запрос: O(M + N). Проходит подзадачи 1-2.

Перебор с вектором (M по остатку)

В векторе все элементы — оставшиеся в кругу персонажи, значит мы можем сразу найти индекс (в векторе) искомого элемента: idx = (idx + M − 1) mod (N − i + 1) (прибавляем M к idx — текущему элементу, отнимаем 1 т.к. сам idx также считается и берём остаток от деления на число оставшихся в круге персонажей).

Асимптотика: O(1) на поиск персонажа; O(N) на удаление персонажа.

Итоговая асимптотика на запрос: O(N). Проходит подзадачи 1-7.

Перебор с вектором (M по остатку, оптимизация по удалению)

Слабое место предыдущего решения — удаление персонажа, т.к. если вектор содержит N элементов, то удаление i-го происходит за O(N − i). Это наиболее невыгодно при малых i, которые медленно растут. Худший вариант — i = 1, 2, 3, 4, .., что возможно при M = 1.

Можно скомбинировать решения: при больших M применять по-прежнему вектор, а при малых M (M ≤ 100) применять тот алгоритм, что наиболее выгоден в этом случае, а именно — прямой перебор, т.к. поиск персонажа осуществляется за O(M) (а мы используем только в случаях M < N).

Асимптотика при больших M: O(1) на поиск персонажа; O(N) на удаление персонажа.

Асимптотика при малых M: O(M) на поиск персонажа; O(1) на удаление персонажа.

Итоговая асимптотика на запрос: O(min(M, N)). Проходит подзадачи 1-8.

Перебор с вектором (M по остатку, sqrt-декомпозиция)

Другим вариантом оптимизации решения с вектором является разбивание круга на несколько векторов. Пусть мы распределили N элементов в S векторов. При этом в каждом векторе будет по NS элементов (т.е. в первом 1, 2, .., S, во втором S + 1, S + 2, .., 2S и т.д.), кроме S-го вектора (в нём будет N mod S элементов), а значит и удаление элемента из любого такого вектора будет происходить уже за O(NS). При этом поиск M-го по счёту элемента от текущего (M как обычно берём по модулю N − i + 1) будет происходить за O(S), т.к. в каждом векторе количество элементов уменьшается с каждым удалением элемента (оно не всегда равно NS), и в худшем случае придётся пройти все S векторов, отнимая количество элементов в них от M, прежде чем M станет меньше или равным номеру последнего элемента в некотором векторе.

Т.к. нам выгоднее сделать сложность удаления и поиска одинаковой (тогда общая сложность будет минимальна), можем найти нужное число S: NS = S, откуда S = √N. Такой подход (разбивание чего-либо на √N блоков) называется "sqrt-декомпозиция".

В реальности число S выгоднее брать немного меньше, ввиду особенностей алгоритма, и подбирать его экспериментальным путём (в авторском решении с sqrt-декомпозицией векторов S = 100).

Асимптотика: O(√N) на поиск персонажа; O(√N) на удаление персонажа.

Итоговая асимптотика на запрос: O(√N). Проходит ВСЕ подзадачи.

Перебор с двусвязным списком (M по остатку)

Создадим двусвязный список, поместим в него по порядку элементы от 1 до N. Далее будем искать M-й по счёту элемент (M как обычно берём по модулю N − i + 1), и удалять его. При этом удаление в списке происходит за O(const).

Асимптотика: O(N) на поиск персонажа; O(const) на удаление персонажа.

Итоговая асимптотика на запрос: O(N + const). Проходит подзадачи 1-4.

Перебор с прыжками по массиву (M по остатку)

Создадим массив размера N, поместим в него по порядку элементы от 1 до N. Для каждого элемента i запомним индекс следующего за ним элемента next_i и предыдущего prev_i. Далее будем искать M-й по счёту элемент (M как обычно берём по модулю N − i + 1), и удалять его следующим образом: next(prev_i) = next_i, prev(next_i) = prev_i, т.е. "связываем" ближайших не удалённых соседей спереди и сзади. На деле это реализация двусвязного списка через массив, но здесь мы работаем без итератора и не тратим время на освобождение памяти после удаления элемента, поэтому данное решение немного быстрее.

Асимптотика: O(N) на поиск персонажа; O(1) на удаление персонажа.

Итоговая асимптотика на запрос: O(N). Проходит подзадачи 1-5.

Перебор с улучшенными прыжками по массиву (M по остатку)

Будем запоминать не одного, а X ближайших соседей спереди и сзади. Тогда мы сможем найти элемент в худшем случае за NX прыжков, а при удалении элемента нам придётся обновлять данные для X соседей спереди и сзади (у каждого из которых надо поменять по X его соседей, итого X² операций).

Т.к. нам выгоднее сделать сложность удаления и поиска одинаковой (тогда общая сложность будет минимальна), можем найти лучшее число X: NX = X², откуда X = ³√N.

В реальности число X выгоднее брать немного меньше, ввиду особенностей алгоритма, и подбирать его экспериментальным путём (в авторском решении X = 40).

Асимптотика: O(³√N²) на поиск персонажа; O(³√N²) на удаление персонажа.

Итоговая асимптотика на запрос: O(³√N²). Проходит подзадачи 1-6.

Перебор с бинарным деревом (M по остатку)

Бинарное дерево — такое дерево, в котором у каждой вершины имеется родительская вершина, две дочерние (левая и правая). Для нумерации вершины используется простой приём: вершина с номером u имеет левую дочернюю вершину с номером u ⋅ 2 и правую с номером u ⋅ 2 + 1. Самая верхняя вершина (у которой нет родительской) имеет номер 1.

Построим бинарное дерево G из N вершин. Листья дерева (т.е. вершина без дочерних вершин) будет содержать в себе индекс персонажа (для листа u это G[u].idx) и номер родительских вершин (G[u].p), все остальные — номера родительской и дочерних вершин (G[u].L, G[u].R), а также количество листьев в поддереве данной вершины (G[u].cnt). При построении дерева запомним лист с номером u, который содержит в себе персонажа под индексом 1. Далее будем перемещаться на M вершин (M как обычно берём по модулю N − i + 1) вперёд, поднимаясь вверх к родительской вершине и спускаясь вниз к следующей (для этого будем использовать информацию о количестве уже пройденных листьев и о количестве листьев в поддереве вершины — если их недостаточно, значит нужно подняться ещё вверх, если мы уже на самой верхней вершине, значит наш путь проходит через конечный лист в начальный, тогда следует разделить переход на два: от текущего к конечному, и от начального к искомому). На самом деле "путь" не проходит через все M вершин, а лишь поднимается по бинарному дереву от текущей вершины (совершая не более log(N) подъёмов), а затем спускается, каждый раз считая, в какую дочернюю вершину стоит спуститься — в левую или в правую (совершая не более log(N) спусков). При этом удаление вершины состоит в уменьшении G[p].cnt на единицу, где p — все родительские вершины данного листа (т.е. не более log(N) уменьшений).

Асимптотика: O(log(N)) на поиск персонажа; O(log(N)) на удаление персонажа.

Итоговая асимптотика на запрос: O(log(N)). Проходит ВСЕ подзадачи.

Перебор с бинарным поиском и суммой на отрезке (M по остатку)

На каждой итерации запустим бинарный поиск, который будет искать отрезок минимальной длины, который содержит нужное количество оставшихся персонажей (M mod N). Для того, чтобы узнать какое количество персонажей всё еще находится на каком-то отрезке, необходимо использовать какую-нибудь структуру данных, которая позволяет делать сумму на отрезке и изменение одного элемента. Например, подойдут дерево Фенвика или дерево отрезков. Как только нашли минимальный отрезок нужной длины — можем удалить соответствующего персонажа из структуры данных.

Чтобы не было сложности в том, что персонажи стоят по кругу, можно заранее увеличить их количество в два раза: тогда каждому персонажу будет соответствовать две ячейки в структуре данных. Это позволит всегда запускать бинарный поиск от 1 до N (M mod N < N) из любой позиции первой половины без необходимости делать переход с последней позиции на первую.

Асимптотика: O(log²(N)) на поиск персонажа; O(log(N)) на удаление персонажа.

Итоговая асимптотика на запрос: O(log²(N)). Проходит ВСЕ подзадачи.

Обратный перебор (M по остатку)

Данное решение отличается от других тем, что мы ищем персонажей в обратном порядке их удаления. 0-ой по счёту персонаж (pos = 0) будет тем, который остался последний. Осталось найти номер того, с кого начинали счёт в самом начале. Для этого N раз (для i = 1..N) проделаем следующее: pos = (pos + M)mod i. Беря остаток по i, которое постоянно увеличивается, мы тем самым "добавляем" персонажей в наш круг, по которому мы считаем кто был последним до каждого счёта. Посчитав в N-ый раз pos, выведем pos + 1, которое и будет ответом на задачу (в этом нетрудно убедится — если бы мы начинали счёт с 0 позиции, тогда закончили бы как раз в позиции pos, а добавить 1 нужно потому, что мы начинали счёт с нуля, для простоты работы с остатками).

При этом решение имеет следующий недостаток — мы не можем найти номера тех, кто выбывал в i-ый раз (2 ≤ i ≤ N − 1), только последнего (т.к. порядок индексов для всех i, кроме N, сдвинут по сравнению с реальным). Но в условиях данной задачи этого не требовалось, следовательно данное решение является наиболее простым и эффективным.

Итоговая асимптотика: O(N). Проходит ВСЕ подзадачи.