Везде, где не указано — время работы $O(n)$, а если есть конкретные числа, то TL 1 секунда.
Задачи идут в порядке вспоминания/придумывания, то есть в весьма рандомном.
#Попугаи
Вам нужно передать 64 байт некоторой информации. Для этого у вас есть 320 специально обученных попугаев, каждый из которых может запомнить число от 0 до 255. Все попугаи рано или поздно долетают до точки назначения и сообщают свой байт, но, возможно, не в том порядке, в котором были выпущены. Попугаи внешне неразличимы.
#Минимум и максимум
Даны 68 камней разного веса. Требуется за 100 операций взвешивания определить самый лёгкий и самый тяжелый.
#Перестановка
Есть перестановка из 64 элементов. Вы можете спрашивать, какие элементы находятся на заданном множестве позиций (вам сообщается список элементов в произвольном порядке). Восстановите перестановку за 6 запросов.
#Выпуклая оболочка
Требуется отвечать на два типа запросов:
- Добавить точку в выпуклую оболочку.
- Проверить, лежит ли точка внутри выпуклой оболочки.
Обе операции онлайн за $O(\log n)$.
#Геометрическая прогрессия
Найдите способ посчитать $\frac{1-a^n}{1-a}$ по произвольному модулю за $O(\log n)$.
#Покемоны
В турнире участвуют 1024 видов покемонов. Вы, будучи экспертом по покемонам, знаете, кто кого может победить. Иначе говоря, вам полностью известен граф-турнир из 1024 вершин и $1023 \times 1022 : 2$ рёбер, в котором каждые две вершины соединены ровно одним ориентированным ребром, определяющим победителя в возможном поединке. Обратите внимание, что из $a \to b$ и $b \to c$ не следует, что $a \to c$.
У вас есть 10 покеболов. Составьте команду из 10 покемонов такую, что для каждого из 1024 типов покемонов в вашей команде найдется покемон, побеждающий его. Считайте, что в битве одинаковых покемонов побеждает ваш.
#Сортировка
Можно ли отсортировать
- 5 камней за 8 взвешиваний?
- 5 камней за 7 взвешиваний?
- 20 камней за 60 взвешиваний?
#Точки в круге
Даны $n$ точек, равномерно распределенных в единичном круге с центром в начале координат. Предложите алгоритм, который за $O(n)$ в среднем сортирует их по удаленности от начала координат.
#Бинарный поиск
На стороне интерактора был сгенерирован массив из $n$ случайных чисел, равномерно распределенных на некотором промежутке, а затем отсортирован. За один запрос можно по индексу в массиве узнать число, которое там лежит. Требуется за $O(\log \log n)$ операций в среднем определять, есть ли в данном массиве число $x$.
#Случайный бинарный поиск
Дан такой бинарный поиск, в котором мы вместо элемента из середины берем случайный:
int lower_bound(int x) {
int l = 0, r = n - 1;
while (l < r) {
int m = l + rand() % (r - l);
if (t[m] >= x)
r = m;
else
l = m + 1;
}
return l;
}
Все ключи и запросы случайные. При $n \to \infty$, во сколько в среднем раз больше итераций рандомизированный бинарный поиск будет делать по сравнению с обычным?
#Замкнутые ломаные
Даны две замкнутые несамопересекающиеся ломаные. Определите, можно ли перевести их друг в друга с помощью параллельного переноса, поворотов и гомотетии?
#Неубывающий массив
Дан массив из $n$ целых чисел. Требуется за $2n$ операций «прибавить к одному элементу любой другой» сделать его неубывающим.
#Чётный цикл
Дан неориентированный граф. Определите, есть ли в нём простой цикл чётной длины.
#$k$-ая порядковая статистика
Дан массив из $n$ целых чисел. Найдите его $k$-й наименьший элемент за $O(n)$.
#Доминирующий элемент
Дан массив из $n$ элементов. Требуется ответить на $m$ запросов, есть ли на отрезке $[l, r]$ доминирующий элемент — тот, который встречается на нём хотя бы $\frac{r-l}{2}$ раз. Время работы $O((n+m) \log n)$.
#Разрушение дерева
Дано корневое дерево. Каждую итерацию выбирается вершина (равновероятно из всех оставшихся), и удаляется всё поддерево, соответствующее этой вершине. Найти, сколько ходов в среднем будет продолжаться этот процесс, то есть матожидание номера итерации, на которой будет удалён корень дерева.
#$k$-ый элемент на отрезке
Дан массив из $n$ целых чисел. Требуется ответить на $m$ запросов $k$-ой порядковой статистики на произвольном отрезке. Время работы $O((n+m) \log n)$.
#Различные числа на отрезке
Дан массив из $n$ целых чисел. Требуется ответить на $m$ запросов количества различных элементов на произвольном отрезке. Время работы $O(m\sqrt{n})$.
#Физкультура
Зачёт по физкультуре в одном институте ставится по количеству посещений, поэтому важно знать, сколько учебных дней осталось до конца семестра (особенно когда напропускал пары). Семестр длится $m$ дней. Деканат последовательно издает $n$ приказов двух типов:
- Объявить все дни с $l$ по $r$ выходными (физру закрывать нельзя)
- Объявить все дни с $l$ по $r$ учебными (физру закрывать можно)
При этом приказ может частично отменить действие предыдущих приказов.
После каждого приказа нужно посчитать суммарное число учебных дней в семестре. Асимптотика $O(n \log n)$.
#Нулевая сумма
Дано мультимножество из $n$ целых чисел. Найдите любое его непустое подмножество, сумма чисел которого делится на $n$.
#Мета-задача
В задаче дана произвольная строка, по которой известным только авторам способом генерируется ответ yes/no. В задаче 100 тестов. У вас есть 20 попыток. В качестве фидбэка вам доступны вердикты на каждом тесте. Вердикта всего два: OK (ответ совпал) и WA. Попытки поделить на ноль, выделить терабайт памяти и подобное тоже считаются как WA. «Решите» задачу.
#Мета-задача 2
Условие как в «Мета-задаче», но сообщается только число пройденных тестов.
100 тестов, 70 попыток.
#Мета-задача 3
Условие как в «Мета-задаче», но сообщается только номер первого не пройденного теста.
10 тестов, 100 попыток.
#Ниточка
В плоскую доску вбили $n$ гвоздей радиуса $r$, причём так, что соответствующие точки на плоскости образуют вершины выпуклого многоугольника. На эти гвозди натянули ниточку, причём ниточка «огибает» по кругу гвозди. Найдите длину ниточки, то есть периметр этого многоугольника с учётом закругления.
#Пельмени
Компания друзей захотела сделать заготовки для пельменей из огромного прямоугольного куска теста. Для этого в ход пошли всевозможные предметы округлой формы: стаканы, кружки, кастрюли… В итоге тесто было разделено $n$ возможно пересекающимися окружностями произвольных радиусов и центров. Нам интересно посчитать, сколько получилось заготовок, то есть на сколько кусков распалось тесто. Асимптотика $O(n^2 \log n)$.
#От нуля до единицы
Дан следующий код:
x = 0
while x < 1:
x += random()
Требуется посчитать матожидание x.
(random в питоне возвращает случайное действительное число от 0 до 1.)
#Площадь
Дан единичный квадрат и 100 кругов. Нужно посчитать площадь квадрата, которую покрывают эти круги, с ошибкой менее 1%.
#Окружности
Имеется окружность радиуса $R$, назовём её внешней. Внутри неё лежит окружность радиуса $r < R$ и соприкасается с ней. Дальше строятся бесконечное число окружностей по следующему правилу: $k$-я окружность должна
- соприкасаться с внешней,
- соприкасаться с предыдущей (($k-1$)-ой),
- иметь при этом максимальный радиус.
Найдите (выведите формулу за $O(1)$) радиус $k$-й такой окружности.
#Блеф
Катя и Серёжа играют в игру. У Кати есть $n$ карт, у Серёжи — $m$. Одна дополнительная карта лежит на столе рубашкой вверх. Назовём её особой. Цель игроков — её отгадать. Все $n+m+1$ карт различны, игроки изначально знают только свои карты. Игроки ходят по очереди, начинает Катя. Игрок в свой ход может:
- Попытаться угадать особую карту. Если получилось угадать, то игрок победил, иначе проиграл. В любом случае, игра на этом заканчивается.
- Назвать любую карту из колоды. Если у соперника есть такая карта — он обязан показать ее и вывести из игры. Если же у него нет такой карты — он сообщает об этом.
С какой вероятностью выиграет Катя при оптимальной игре обоих игроков? Асимптотика $O(nm)$.
#Достижимость
Дан ориентированный граф без кратных рёбер. Для всех пар вершин $u$ и $v$ определите, можно ли дойти из $u$ в $v$. Вершин меньше 2000.
#Нумизмат
Есть $n$ жадных коллекционеров монет, которые согласны меняться, только если взамен монеты, которых у них более одной, они получают монету, которых у них нет вовсе. Всего есть $k$ типов монет. Известно количество монет каждого типа у каждого коллекционера и у коллекционера Серёжи. Серёжа хочет максимизировать количество различных монет у него путем обмена с жадными коллекционерами. Считайте, что жадные коллекционеры не меняются между собой.
Придумайте любой полиномиальный алгоритм.
#Принцесса
В некотором королевстве жила принцесса. Она была настольно прекрасна, что каждый юноша в королевстве хотел жениться на ней. Принцесса была привередлива, поэтому твердо решила выйти замуж только за самого красивого юношу в государстве.
Она составила список из $n$ самых красивых юношей и вызывает их каждый день в случайном порядке. После того, как к ней приходит очередной юноша, она принимает решение: либо выйти за него замуж, либо нет. Если она выходит за него замуж, то она все равно просматривает всех остальных, чтобы убедиться, что он действительно самый красивый. Если это так, то они живут долго и счастливо. Если нет (если она вышла замуж не за самого красивого, либо не вышла замуж вообще), то принцесса покончит жизнь самоубийством.
У принцессы очень хорошая память, поэтому она может сравнивать красоту очередного юноши со всеми предыдущими, а также у неё тонкий вкус, поэтому никакие двое юношей не являются для неё одинаково красивыми.
Помогите принцессе разработать стратегию, которая максимизирует вероятность того, что она выйдет замуж за наиболее красивого юношу.
Асимптотика $O(n^2)$.
#Спираль
Определим спираль $(2n+1) \times (2n+1)$ как матрицу следующего вида:
$$ \begin{matrix} 21 & 22 & 23 & 24 & 25 \\ 20 & 7 & 8 & 9 & 10 \\ 19 & 6 & 1 & 2 & 11 \\ 18 & 5 & 4 & 3 & 12 \\ 17 & 16 & 15 & 14 & 13 \\ \end{matrix} $$Ваша задача — рассчитать ответы на $q$ запросов суммы чисел в произвольной прямоугольной области (по модулю $10^9+7$).
$q \leq 100$, $n \leq 10^9$.
#Польский лабиринт
Группа из $n$ туристов гуляет в бесконечном лабиринте. Лабиринт имеет форму треугольника Серпинского: клетка $(x, y)$ свободна, только если x & y == 0.
Туристы устали блуждать по лабиринту и хотят встретиться в какой-нибудь свободной клетке, сумма расстояний от всех туристов до которой наименьшая. Туристы за один ход могут передвигаться вверх, вниз, влево и вправо по свободным клеткам.
$n \leq 10^5$, изначальные координаты туристов до $10^9$.
#Нимные подмножества
Есть множество $A$, состоящее из $n$ чисел от 0 до $2^{32}-1$. Требуется выбрать его подмножество $B \subseteq A$ максимальной суммы такое, что нельзя выбрать его подмножество $C \subseteq B$ такое, что ним на кучках соответствующего размера — проигрышный. Асимптотика $O(n \log n)$.
#Баланс степеней
Дан неориентированный граф. Требуется ориентировать каждое ребро так, чтобы максимизировать число вершин, у которых степень исхода равна степени захода.
#Два пути
Дан ориентированный граф. Найдите два непересекающихся по рёбрам пути из $s$ в $t$.
#Пьяница
Пьяница стоит на числовой прямой в точке 0. Каждую секунду он делает единичный шаг вправо (в сторону увеличения координат) с вероятностью $p$ и влево с вероятностью $1-p$. С какой вероятностью он когда-либо окажется в точке с отрицательной координатой?
#Ксоровый рюкзак
Дан массив из $10^5$ целых чисел от $0$ до $(2^{30}-1)$. Найти количество различных подпоследовательностей этого массива, xor-сумма которых равна заданному числу $x$.
#Иван Сусанин
Польская армия хочет добраться из поселения $s$ в поселение $t$. Ей руководят два гетмана — Камиль и Матеуш.
- Камиль руководит армией днём и водит армию по дорогам.
- Матеуш руководит армией ночью и совершает маневры по секретным тропам.
Каждый гетман перед маршем спрашивает дорогу у Ивана Сусанина. Иван хочет задержать наступление польских войск.
Карта дорог известна Камилю. Аналогично, карта секретных троп известна Матеушу. Поэтому Ивану не удастся их так просто обмануть — он должен каждый раз выбрать переход так, что минимальное расстояние между поселением $t$ и войском по соответствующей карте строго уменьшилось.
Вы знаете карту дорог и троп вместе с их длинами. Помогите Ивану как можно дольше (желательно, бесконечно) вести армию из $s$ в $t$.
#Варенье
В ряд стоят $n$ пустых банок из-под варенья. Вместительность $i$-й банки равна $v_i$ грамм.
Карлсон наполняет эти банки вареньем в $m$ этапов. На каждом этапе он выбирает числа $l$, $r$, $x$ и $y$, а затем пролетает над банками с $l$ по $r$, выполняя следующие операции: в банку номер $l$ он добавляет $x$ грамм варенья, в банку номер $(l + 1)$ — $(x + y)$ грамм варенья, в банку номер $(l + 2)$ — $(x + 2y)$, и так далее до $r$-той банки, в которую он положит $x + y(r - l)$ грамм варенья.
Малышу хочется определить для каждой банки наименьший номер операции, после которой она станет полной.
$n, m \leq 10^5$
#Лабиринт
Серёжа потерялся в лабиринте $n \times m$. Каждая клетка либо свободна, либо стена. Все крайние клетки — стены. Вам известно, где находится выход из лабиринта, но не известно, где находится Серёжа. Составьте для него последовательность направлений (вверх, вниз, влево, вправо) такую, после которой он окажется в клетке с выходом, вне зависимости от его стартовой позиции. Если вы прикажете ему идти в стену, то просто ничего не произойдёт.
Придумайте любой полиномиальный алгоритм.
#Обезьяна
Дана строка из $10^5$ символов латинского алфавита. Обезьяна нажимает случайные клавиши на клавиатуре (одну из 26 букв), пока не наберёт её целиком, то есть пока исходная подстрока не станет подстрокой набранной строки. Какое ожидание числа нажатых клавиш перед тем, как это произойдёт?
#Ожидание минимума
Даны $n$ случайных величин, равномерно распределенных на отрезках $[l_i, r_i]$ — у каждой величины свой отрезок. Найдите математическое ожидание минимума этих случайных величин.
Придумайте любой точный полиномиальный алгоритм.
#Шумный ксор
Загадано некое число $x$. Вы можете делать запросы следующего типа: назвать число $y$ и получить в ответ число единичных битов в ксор-сумме $x$, $y$ и $m$, где $m$ это случайно сгенерированная маска, в которой каждый бит имеет вероятность $p = \frac15$ быть единичным, то есть каждый бит $x \oplus y$ заменяется на противоположный с вероятностью $y$, и вам возвращается количество единичных битов. Для ясности:
x = # ...
def mask(p=0.2):
r = 0
for i in range(32):
if random.random() < p:
r += 2**i
return r
def query(y):
return bin(x ^ y ^ mask()).count('1')
Ваша задача — отгадать число, используя не более 10000 попыток.
#Коммивояжер
Даны $3 \cdot 10^5$ точек на плоскости. Выберите среди них любое подмножество из 500 точек и решите для него задачу коммивояжера: найдите минимальный по длине цикл, проходящий через все эти точки.
#Анаграммы
Найдите в строке $s$ первую подстроку, являющуюся анаграммой (пререстановкой символов) строки $t$ за $O(n)$.
#Функциональный граф
Дан ориентированный граф из $n < 10^5$ вершин, в котором из каждой вершины ведет ровно одно ребро. Требуется ответить на $q < 10^5$ запросов «в какую вершину мы попадем, если начнем в вершине $v_i$ и сделаем $k_i < 10^{18}$ переходов» за время $O(q + n)$.
#Асинхронная шляпа
Серёжа и его $(n - 1)$ друзей решили поиграть в «шляпу», в которой один игрок должен за ограниченное время объяснить как можно больше слов, чтобы его партнер их отгадал.
Каждый игрок должен пообщаться с любым другим по разу; обычно игра проводится так:
- 1-й игрок объясняет в течение минуты слова 2-му,
- 2-й игрок объясняет слова 3-му,
- …,
- $n$-й игрок объясняет слова 1-му,
- 1-й игрок объясняет слова 3-му,
- 2-й игрок объясняет слова 4-му…
…и так далее, пока $(n-1)$-й игрок не закончит объяснять слова $(n-2)$-ому.
Если друзей собралось много, то игра может занять приличное время. Серёжу интересует, какое минимальное время она может длиться, если разрешить парам участников общаться между собой одновременно и в любом порядке.
Для данного $n \le 500$, найдите минимальное количество времени $k$ и соответствующее ему расписание.
#Random coffee
В компании, в которой вы работаете, устроено неизвестное число людей — от одного до бесконечности с равной вероятностью. Для борьбы с одиночеством, каждый сотрудник участвует в «random coffee»: каждую неделю вы встречаетесь со случайным человеком из компании, чтобы попить кофе и обсудить что угодно.
Вы участвовали в random coffee $n$ раз и пообщались с $k$ разными людьми (с некоторыми — более одного раза). Какое наиболее вероятное число человек работает в компании?
#Мафия
В «мафию» играют 13 человек, из которых 10 мирных и 3 мафии. Все роли розданы с помощью стандартной колоды игральных карт: заранее выбрали и перемешали 10 красных и 3 чёрные карты, кто вытянул черную — мафия. Все карты различны и известны всем. Игра начинается с дневного голосования.
Как мирным гарантированно победить?