A. Очередь

Давайте хранить объекты очереди в массиве, добавляя новые элементы в конец массива. Но чтобы не перемещать все элементы очереди при удалении элемента, будем просто считать, что начало очереди смещается.

Такой реализации уже хватит для сдачи задачи. Но тогда место удалённых элементов будет потерянной областью памяти. Чтобы бороться с этой проблемой можно изредка изменять очередь полностью. Если в начале очереди накопилось слишком много неиспользованных ячеек (например, столько же, сколько элементов в самой очереди), то можно сразу удалить все эти ячейки, скопировав все элементы очереди в начало массива. То есть мы будем операцию реального удаления элементов выполнять редко, но удалять сразу же много элементов, тогда средняя сложность в пересчёте на одну операцию удаления будет \(O(1)\).

Есть и другой интересный способ реализации очереди. Если последовательность элементов положить в стек, а потом излечь, то она развернётся в обратном порядке. Если это повторить ещё раз, то последовательность элементов опять развернётся и порядок будет исходным. Очередь же не меняет порядок элементов, поэтому можно реализовать очередь с использованием двух стеков.

B. Стек

Очевидно реализуется через динамический массив.

C. Два стека

Необходимо создать два стека и поддерживать счетчик текущего натурального числа.

D. Стек максимума

Будем хранить два стека: в одном будут сами значения, а в другом стеке для каждого элемента будет храниться максимальное значение во всём стеке, когда мы добавили этот элемент.

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

E. Правильная скобочная последовательность 1

Скобочная последовательность правильная, если для каждой правой скобки мы можем сопоставить в пару левую скобку того же типа, находящуюся слева от правой.

Тогда мы можем поддерживать счетчик суммы на префиксе скобочной последовательности. Если мы видим левую скобку, то прибавлять в этот счетчик один, а если правую – вычитать.

На каждой итерации этот счетчик должен быть не отрицательным, а в конце равным нулю.

F. Правильная скобочная последовательность 2

Закрывающая скобка должна быть парной к последней открывающей. То есть если мы будем хранить последовательность из открывающих скобок, то закрывающая скобка удаляет последнюю открывающую, если она того же вида, в противном случае скобочная последовательность неправильная. Это означает, что последовательность открывающих скобок, которые не были ещё закрыты, представляет собой стек. Если мы встретили открывающую скобку, то она добавляется в конец стека. Если мы встретили закрывающую скобку, то должны выполняться следующие условия: стек не пуст и на вершине стека хранится скобка, парная данной закрывающей скобке. Если после обработки всех скобок стек оказался пуст, то последовательность правильная.

G. Односвязный список

Можно простро создать массив. При добавленни элемента вставлять его в конец массив. При операции go двигать индекс.

H. Дек

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

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

При добавлении еще одного шара сверху количество операций, необходимых для удаления, у шаров снизу не изменится. Количество операции для удаления этого шара будет равно количеству операций, когда все шары с меньшим временем удаления пропадут, и очередь удаления дойдет до нашего шара. То есть \(2 * (size - x) + 1\), где \(size\) – размер дека и \(x\) – количество шаров с меньшим временем удаления.

При добавлении нового шара снизу количество операций для удаления нашего шара будет \(0\). Среди шаров, которые стоят сверху нашего, количество оперций при удалении изменится только у тех, у которых время удаления меньше времени удаления нашего шара. Всего операций прибавится \(2 * x\), где \(x\) – количество шаров с меньшим временем удаления.

Если решить простейшее неравенство, получим, что вставлять новый шар свеху выгодно, когда \(2*x > size\), иначе нужно вставлять снизу.

При удалении необходимо найти позицию элемента в деке. Это можно сделать за \(O(log(n))\), если при добавлении сохранять позицию элемента. Например, можно поддерживать нижний и верхний индексы дека (изначально они равны \(q\) и \(q+1\)), и при добавлении инкрементировать соответствующий индекс в дереве фенвика. Тогда, чтобы найти позицию элемента, достаточно найти сумму на отрезке от одного до номера текущего элемента. Нахождение количества элементов с меньшим временем удаления можно реализовать таким же образом.

Асимптотика \(O(q * log(n))\)

I. Гоблины и шаманы

Можно создать две очереди от начала до середины и от середины до конца.